Solution

Approach #1 Brute Force [Time Limit Exceeded]

Algorithm

The naive approach to solve this problem is to use recursion and backtracking. For finding the solution, we check every possible prefix of that string in the dictionary of words, if it is found in the dictionary, then the recursive function is called for the remaining portion of that string. And, if in some function call it is found that the complete string is in dictionary, then it will return true.

Complexity Analysis

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

• Space complexity : $$O(n)$$ . The depth of the recursion tree can go upto $$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 a particular string. To avoid this we can use memoization method, where an array $$memo$$ is used to store the result of the subproblems. Now, when the function is called again for a particular string, value will be fetched and returned using the $$memo$$ array, if its value has been already evaluated.

With memoization 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 : $$O(n^2)$$ . Size of recursion tree can go up to $$n^2$$ .

• Space complexity : $$O(n)$$ . The depth of recursion tree can go up to $$n$$ .

Approach #3 Using Breadth-First-Search [Accepted]

Algorithm

Another approach is to use Breadth-First-Search. Visualize the string as a tree where each node represents the prefix upto index $$end$$ . Two nodes are connected only if the substring between the indices linked with those nodes is also a valid string which is present in the dictionary. In order to form such a tree, we start with the first character of the given string (say $$s$$ ) which acts as the root of the tree being formed and find every possible substring starting with that character which is a part of the dictionary. Further, the ending index (say $$i$$ ) of every such substring is pushed at the back of a queue which will be used for Breadth First Search. Now, we pop an element out from the front of the queue and perform the same process considering the string $$s(i+1,end)$$ to be the original string and the popped node as the root of the tree this time. This process is continued, for all the nodes appended in the queue during the course of the process. If we are able to obtain the last element of the given string as a node (leaf) of the tree, this implies that the given string can be partitioned into substrings which are all a part of the given dictionary.

The formation of the tree can be better understood with this example: !?!../Documents/139_Word_Break.json:1000,563!?!

Complexity Analysis

• Time complexity : $$O(n^2)$$ . For every starting index, the search can continue till the end of the given string.

• Space complexity : $$O(n)$$ . Queue of atmost $$n$$ size is needed.

Approach #4 Using Dynamic Programming [Accepted]:

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. We make use of $$\text{dp}$$ array of size $$n+1$$ , where $$n$$ is the length of the given string. We also use two index pointers $$i$$ and $$j$$ , where $$i$$ refers to the length of the substring ( $$s'$$ ) considered currently starting from the beginning, and $$j$$ refers to the index partitioning the current substring ( $$s'$$ ) into smaller substrings $$s'(0,j)$$ and $$s'(j+1,i)$$ . To fill in the $$\text{dp}$$ array, we initialize the element $$\text{dp}[0]$$ as $$\text{true}$$ , since the null string is always present in the dictionary, and the rest of the elements of $$\text{dp}$$ as $$\text{false}$$ . We consider substrings of all possible lengths starting from the beginning by making use of index $$i$$ . For every such substring, we partition the string into two further substrings $$s1'$$ and $$s2'$$ in all possible ways using the index $$j$$ (Note 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 $$\text{true}$$ , i.e. if the substring $$s1'$$ fulfills the required criteria. If so, we further check if $$s2'$$ is present in the dictionary. If both the strings fulfill the criteria, we make $$\text{dp}[i]$$ as $$\text{true}$$ , otherwise as $$\text{false}$$ .

Complexity Analysis

• Time complexity : $$O(n^2)$$ . Two loops are their to fill $$\text{dp}$$ array.

• Space complexity : $$O(n)$$ . Length of $$p$$ array is $$n+1$$ .

Analysis written by: @vinod23