Summary

Given a string $$s$$ and a dictionary of words $$dict$$ , add spaces in $$s$$ to construct every possible sentence such that each word is valid as per the given dictionary.\nReturn all such possible sentences.

Solution

Approach #1 Brute Force [Time Limit Exceeded]

Algorithm

The naive approach to solve this problem is to use recursion.\nFor finding the solution, we check every possible prefix of that string ( $$s$$ ) in the dictionary of words, if it is found in the dictionary (say $$s1$$ ), then the recursive function is called for the remaining portion of that string.\nThis function returns the prefix $$s1$$ appended by the result of the recursive call using the remaining portion of the string ( $$s-s1$$ ), if the remaining portion is a substring\nwhich can lead to the formation of a valid sentence as per the dictionary. Otherwise, empty list is returned.

Complexity Analysis

\n
• \n

  Time complexity : $$O(n^n)$$ . Consider the worst case where $$s=``aaaaaaa"$$ and every prefix of $$s$$ is present in the dictionary of words, then the recursion tree can grow up to $$n^n$$ .

  \n
\n
• \n

  Space complexity : $$O(n^3)$$ . In worst case the depth of recursion tree can go up to $$n$$ and nodes can contain $$n$$ strings each of length $$n$$ .

  \n
\n

Approach #2 Recursion with memoization [Accepted]

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\n multiple paths.\nTo avoid this we can use memorization method, where we are making use of a hashmap to store the results in the form of a $$key:value$$ pair. In this hashmap, the $$key$$ \n used is the starting index of the string currently considered and the $$value$$ contains all the sentences which can be formed using the substring from this starting\n 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\n 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

\n
• \n

  Time complexity : $$O(n^3)$$ . Size of recursion tree can go up to $$n^2$$ . The creation of list takes $$n$$ time.

  \n
\n
• \n

  Space complexity : $$O(n^3)$$ .The depth of the recursion tree can go up to $$n$$ and each activation record can contains a string list of size $$n$$ .

  \n
\n

Approach #3 Using Dynamic Programming [Time Limit Exceeded]:

Algorithm

The intuition behind this approach is that the given problem ( $$s$$ ) can be divided into subproblems $$s1$$ and $$s2$$ . If these subproblems individually satisfy the required conditions, the complete problem, $$s$$ 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 $$\\text{dp}$$ array formation.\nWe make use of $$\\text{dp}$$ array (in the form of a linked list) of size $$n+1$$ , where $$n$$ is the length of the given string.\n $$\\text{dp}[k]$$ is used to store every possible sentence having all valid dictionary words using the substring $$s[0:k-1]$$ .\n We also use two index pointers $$i$$ and $$j$$ , where $$i$$ refers to the length of the substring ( $$s\'$$ ) considered currently starting from\nthe beginning, and $$j$$ refers to the index partitioning the current substring ( $$s\'$$ ) into smaller substrings $$s\'(0,j)$$ and $$s\'(j+1,i)$$ .\nTo fill in the $$\\text{dp}$$ array, we initialize the element $$\\text{dp}[0]$$ as an empty string, since no sentence can be formed using a word of size 0.\nWe consider substrings of all possible lengths starting from the beginning by making use of index $$i$$ .\nFor every such substring, we partition the string into two further substrings $$s1\'$$ and $$s2\'$$ in all possible ways using the index $$j$$ (\nNote that the $$i$$ now refers to the ending index of $$s2\'$$ ). Now, to fill in the entry $$\\text{dp}[i]$$ , we check if the $$\\text{dp}[j]$$ contains a non-empty string\n i.e. if some valid sentence can be formed using $$s1\'$$ . If so, we further check if $$s2\'$$ is present in the dictionary. If both the conditions are satified,\n we append the substring $$s2\'$$ to every possible sentence that can be formed up to the index $$j$$ (which is already stored in $$d[j]$$ ). These newly formed sentences\n are stored in $$\\text{dp}[i]$$ . Finally the element $$\\text{dp}[n]$$ ( $$n$$ refers to the length of the given string $$s$$ ) gives all possible valid sentences using the complete string $$s$$ .

Complexity Analysis

\n
• \n

  Time complexity : $$O(n^3)$$ . Two loops are required to fill $$\\text{dp}$$ array and one loop for appending a list .

  \n
\n
• \n

  Space complexity : $$O(n^3)$$ . Length of $$\\text{dp}$$ array is $$n$$ and each value of $$\\text{dp}$$ array contains a list of string i.e. $$n^2$$ space.

  \n
\n

Analysis written by: @vinod23