Given a string "s" and an array of words "words," find out if "s" can be segmented into a space-separated sequence of words contained in the array.
Note: From the array "words []," each word can be taken any number of times and in any order.
Example
Input: s="busylivingdying", words[] = {"Get", "busy", "living", "or", "get", "dying"}, Output: true
Example
Input: s="liveagainonce", words[] = {"you", "only", "live", "once"}, Output: false
Solutions
Method 1: In O(n^2) time and O(n) space
This method includes using an extra "set" to store words so that we can check their existence in O(1) time.
The idea is to keep appending the current character to the "tmp" string and check if "tmp" is present in the array.
If any instance of the "tmp" string is present in the array, check the remaining sub-string recursively.
If "tmp" and the remaining sub-string are both recursively present in the array, than return "true"; otherwise, return "false".
Complexity
The time complexity of this solution is O(n^2) and space complexity is O(n).