## 139. Word Break

Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words. You may assume the dictionary does not contain duplicate words.

For example, given
s = "leetcode",
dict = ["leet", "code"].

Return true because "leetcode" can be segmented as "leet code".

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.

b'
\n\n

## Solution

\n
\n

#### Approach #1 Brute Force [Time Limit Exceeded]

\n

Algorithm

\n

The naive approach to solve this problem is to use recursion and backtracking.\nFor 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.

\n\n

Complexity Analysis

\n
\n
• \n

Time complexity : . Consider the worst case where and every prefix of is present in the dictionary of words, then the recursion tree can grow upto .

\n
• \n
• \n

Space complexity : . The depth of the recursion tree can go upto .

\n
• \n
\n
\n

#### Approach #2 Recursion with memoization [Accepted]

\n

Algorithm

\n

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 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 array, if its value has been already evaluated.

\n

With memoization many redundant subproblems are avoided and recursion tree is pruned and thus it reduces the time complexity by a large factor.

\n\n

Complexity Analysis

\n
\n
• \n

Time complexity : . Size of recursion tree can go up to .

\n
• \n
• \n

Space complexity : . The depth of recursion tree can go up to .

\n
• \n
\n
\n

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

\n

Algorithm

\n

Another approach is to use Breadth-First-Search. Visualize the string as a tree where each node represents the prefix upto index .\nTwo 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.\nIn order to form such a tree, we start with the first character of the given string (say ) 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 ) 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 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.

\n

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

\n\n

Complexity Analysis

\n
\n
• \n

Time complexity : . For every starting index, the search can continue till the end of the given string.

\n
• \n
• \n

Space complexity : . Queue of atmost size is needed.

\n
• \n
\n
\n

#### Approach #4 Using Dynamic Programming [Accepted]:

\n

Algorithm

\n

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.

\n

Now, we\'ll move onto the process of array formation. We make use of array of size , where is the length of the given string. 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 , since the null string is always present in the dictionary, and the rest of the elements of as . 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 , i.e. if the substring fulfills the required criteria. If so, we further check if is present in the dictionary. If both the strings fulfill the criteria, we make as , otherwise as .

\n\n

Complexity Analysis

\n
\n
• \n

Time complexity : . Two loops are their to fill array.

\n
• \n
• \n

Space complexity : . Length of array is .

\n
• \n
\n
\n

Analysis written by: @vinod23

\n
'