Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, add spaces in s to construct a sentence where each word is a valid dictionary word. You may assume the dictionary does not contain duplicate words.
Return all such possible sentences.
For example, given
s = "catsanddog",
dict = ["cat", "cats", "and", "sand", "dog"].
A solution is ["cats and dog", "cat sand dog"].
UPDATE (2017/1/4):
The wordDict parameter had been changed to a list of strings (instead of a set of strings). Please reload the code definition to get the latest changes.
Given a string and a dictionary of words , add spaces in to construct every possible sentence such that each word is valid as per the given dictionary. Return all such possible sentences.
Algorithm
The naive approach to solve this problem is to use recursion. For finding the solution, we check every possible prefix of that string () in the dictionary of words, if it is found in the dictionary (say ), then the recursive function is called for the remaining portion of that string. This function returns the prefix appended by the result of the recursive call using the remaining portion of the string (), if the remaining portion is a substring which can lead to the formation of a valid sentence as per the dictionary. Otherwise, empty list is returned.
Complexity Analysis
Time complexity : . Consider the worst case where and every prefix of is present in the dictionary of words, then the recursion tree can grow up to .
Space complexity : . In worst case the depth of recursion tree can go up to and nodes can contain strings each of length .
Algorithm
In the previous approach we can see that many subproblems were redundant, i.e we were calling the recursive function multiple times for the same substring appearing through multiple paths. To avoid this we can use memorization method, where we are making use of a hashmap to store the results in the form of a pair. In this hashmap, the used is the starting index of the string currently considered and the contains all the sentences which can be formed using the substring from this starting index onwards. Thus, if we encounter the same starting index from different function calls, we can return the result directly from the hashmap rather than going for redundant function calls.
With memorization many redundant subproblems are avoided and recursion tree is pruned and thus it reduces the time complexity by a large factor.
Complexity Analysis
Time complexity : . Size of recursion tree can go up to . The creation of list takes time.
Space complexity : .The depth of the recursion tree can go up to and each activation record can contains a string list of size .
Algorithm
The intuition behind this approach is that the given problem () can be divided into subproblems and . If these subproblems individually satisfy the required conditions, the complete problem, also satisfies the same. e.g. "catsanddog" can be split into two substrings "catsand", "dog". The subproblem "catsand" can be further divided into "cats","and", which individually are a part of the dictionary making "catsand" satisfy the condition. Going further backwards, "catsand", "dog" also satisfy the required criteria individually leading to the complete string "catsanddog" also to satisfy the criteria.
Now, we'll move onto the process of array formation. We make use of array (in the form of a linked list) of size , where is the length of the given string. is used to store every possible sentence having all valid dictionary words using the substring . We also use two index pointers and , where refers to the length of the substring () considered currently starting from the beginning, and refers to the index partitioning the current substring () into smaller substrings and . To fill in the array, we initialize the element as an empty string, since no sentence can be formed using a word of size 0. We consider substrings of all possible lengths starting from the beginning by making use of index . For every such substring, we partition the string into two further substrings and in all possible ways using the index ( Note that the now refers to the ending index of ). Now, to fill in the entry , we check if the contains a non-empty string i.e. if some valid sentence can be formed using . If so, we further check if is present in the dictionary. If both the conditions are satified, we append the substring to every possible sentence that can be formed up to the index (which is already stored in ). These newly formed sentences are stored in . Finally the element ( refers to the length of the given string ) gives all possible valid sentences using the complete string .
Complexity Analysis
Time complexity : . Two loops are required to fill array and one loop for appending a list .
Space complexity : . Length of array is and each value of array contains a list of string i.e. space.
Analysis written by: @vinod23