Word Break Problem

Problem Statement

In the word break problem, you will be given a string, say s, and a dictionary of strings say wordDict. The wordDict will contain several strings.

Now, our job is to determine if we can break or segment the string using the words in the dictionary. If we can do that, then we return a True, otherwise, we return a False. We will better understand this through examples ahead.

Must Note: You must note that, while we are breaking the string, we can reuse the same word in the dictionary multiple times. That is, picking the same word multiple times from the dictionary, for forming the string S is allowed.

Task: Break the words in the string S in such a way that, the segmented words are present in the dictionary. Finally, return True, if it is possible to break the word in that manner. Otherwise, return a False.

Input Format: You will be given the string S. And a dictionary of strings wordDict.

Example

Let us look into some examples to understand the problem better.

Example 1:

Input:

Output:

Explanation: The above input is "storybook". It can be split into "story" and " book". So, since it can be split, we return a True as output.

Example 2:

Input:

Output:

Explanation: The above input is "monkeyandonkey". It can be split into "monkey", "and" and "onkey". Or, say "monkey", " an" and "donkey" (there can be several other splits made). However, please note that it cannot be formed from the words given in the dictionary. For example, if we combine them, it will result in "monkeyanddonkey" instead of "monkeyandonkey". Please notice the extra 'd' here. So, a false is returned.

Constraints

The constraints for the problem are given below:-

Constraints:

• 1 <= s.length <= 300
• 1 <= wordDict.length <= 1000
• 1 <= wordDict[i].length <= 20
• s and wordDict[i] consist of only lowercase English letters.
• All the strings of wordDict are unique.

Intuition for the problem

Solving word break is something like taking the word pieces from the word dictionary and trying to construct our target word.

Have you ever played a puzzle game? In that case, you have already solved wordbreak.

You can think of the pieces of the puzzle as the words in the dictionary, and the final puzzle as the complete word.

To solve the word game here, we can do two things:

1. Start with the valid word (say "storybook") and try to break it down into the words in the dictionary. This approach is also popularly known as the Top-down Approach.
2. The second approach you can follow is, to start from an empty word, and keep on building the words till you find that yes, that word exists in the dictionary. This approach is also popularly known as the Bottom Up Approach.

If you can break them down, then you can confirm that, yes word-break is possible and return a True. Otherwise, return a False, because word-break is not possible.

Approach 1: Brute Force - Recursion & Backtracking

Let us begin the analysis of the problem with the brute force approach first. So, as you can see, this problem is majorly about picking or not picking every substring of the word given to us, in the string s and verifying whether that substring exists in the wordDict dictionary or not. This check we will have to perform till the end of the string.

By the above analysis, you might have understood that this can be considered a recursion and backtracking problem. Why? Because you will pick up every possible substring and at each step recursively check whether that substring is a valid word break or not.

But why recursion? Simply because, at every step, we are going to repeatedly ask the same question again and again whether it is a valid wordbreak or not, on a smaller and smaller version of the substring.

Algorithm:

• Declare a recursive function that takes the string, wordDict and the starting position of the string as input.
• The base case will be to check whether our whole string is exhausted, in that case, we can return a true. Because, in that case, we can conclude that the whole string is present in the dictionary.
• Then, to find out the solution, we check every possible prefix of the string in the dictionary of words.
• If the substring is found in the worddict, we recursively call our function for the remaining portion of our string.
• If the substring is not found and all the substrings are being checked, then we simply return a False and exit from our function.

Implementation in C++, Java and Python

C++ Implementation

Below given is the C++ code for the above brute force approach.

Code:

Python Implementation

Below given is the Python code for the above brute force approach.

Code:

Output:

Java Implementation

Below given is the Java code for the above brute force approach.

Code:

Time Complexity Analysis

As you can see, our above-implemented solution is a recursive solution. Also, for a given word of length $N$ (suppose), there are $N+1$ ways to split it into two parts. So, for every step, we will have two choices -- either to split the string or not split the string. Also, in the worst case, we might have to check all the possibilities, thereby applying split and not-split for every substring.

So, in simple words, the time taken in the worst case will be $O(2^{\text{n+1}})$, which is equivalent to $O(2^n)$.

Space Complexity Analysis

As you might already know, the space taken by a recursive solution is equivalent to the recursive stack space, here also we have a similar situation. In this problem, the recursive stack can grow up to a maximum of depth $N$, where $N$ is the length of our word. Hence, the worst-case space taken will be equivalent to $O(N)$.

Approach 2: Recursion with Memoization

Recursion is cool because it breaks our most complicated problems into very simple subproblems. But, for a few of the recursive problems, there is a cost incurred with it -- multiple calls to the same sub-problem. Let us understand it further with an example. Did you notice one thing in our previous approach? We had multiple calls to the same sub-problem, although it was already solved in some recursion steps.

For example, in the above image, suppose we have a string s = "abcd". Now, in the recursive diagram you can see, how we have broken the problem into several subproblems. But, one thing to notice here is that there are multiple calls made to the same function, which were already computed. For example, WB("cd") and WB("d"), are called multiple times in our code, although we have already computed them. As the size of our input will grow, the number of repeating sub-problems will also grow.

So, to avoid the above issue, we can use the memoization technique. Basically, in the memorization method, an array is used to store the results of the already computed sub-problems. Now, when the function is again called for any particular string, the value is fetched and returned from that array (only if its value has already been evaluated).

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

Let us look into the code below.

Implementation in C++, Java and Python

C++ Implementation

Below given is the C++ code for the above recursion with the memoization approach.

Code:

Python Implementation

Below given is the Python code for the above recursion with the memoization approach.

Code:

Output:

Java Implementation

Below given is the Java code for the above recursion with the memoization approach.

Code:

Time Complexity Analysis

In the above code, we will not have to compute the repetitive sub-problems, leading to a drastic improvement in the time complexity. Firstly the size of the recursion tree can grow up to $N^2$, considering $N$ to be the size of the string. At each step of recursion, we will also be computing the substring, which will take another $O(N)$. Hence the worst-case time complexity would be equal to $O(N^3)$.

Space Complexity Analysis

Since you may already be aware, that the space occupied by a recursive solution is equal to the space occupied by the recursive stack, the situation here is also comparable. The recursive stack in this problem can expand to a maximum depth of $N$, where $N$ is the length of our word. The worst-case space taken will therefore be $O(N)$.

Approach 3 - Using Breadth First Search

The next approach we will see is using the breadth-first search to solve this problem.

Here we consider the string to be a tree, with each node representing the prefix up to the end index. We can visualize the string as a tree, where every node will represent the prefix up to the end index. Let us look into the algorithm to solve using this approach:

Algorithm:

• Firstly, we will create a set of the wordDict to store all the unique words of the wordDict passed to us.
• Also, we will take two variables, q (which is a deque to store the end index of the string which is present in the wordDict) and visited (which will store the starting index of the string which is present in the wordDict).
• We will run a loop through the q, and at each step, we will do the following:
  • Pop the left element from the q into the start variable.
  • If start is already present in the visited list, we will not do anything, and skip that iteration.
  • Otherwise, we run a for-loop named end (say) through start till the length of the string i.e. len(s).
  • Inside the loop we check if the substring starting from start till end is present in the wordDict or not.
  • If the substring is present, then we add the end index of the substring into our q data structure.
  • Else we skip and do nothing
  • At any point if the end variable becomes equal to the length of the string, i.e. len(s), then return a True and come out of the iterations.
• We will also add the start to our visited data structure every time we come out of the loop.

Let us not look at the implementation below to understand our code better.

Implementation in C++, Java and Python

C++ Implementation

Below given is the C++ code for the above breadth-first search approach.

Code:

Python Implementation

Below given is the Python code for the above breadth-first search approach.

Code:

Output:

Java Implementation

Below given is the Java code for the above breadth-first search approach.

Code:

Time Complexity Analysis

Let us suppose, the length of the string is $N$.

If we observe the code, we have basically three iterations going on --

• First is the while loop which iterates through the q data structure. In the worst case, it can run till $N$ times.
• Second if the for-loop which runs from start till the length of the string. It can also run to approximately $N$ times in the worst case.
• Third is the substring we take out at every step. It will take another $O(N)$ time

So, overall we have the worst case time complexity is $O(N^3)$

Space Complexity Analysis

We are using a queue data structure, visited list, and another data structure to store the dictionary into a set. So, we can consider that the overall worst-case space taken will be $O(N)$.

Approach 4: Using Dynamic Programming

We have already used the memoization approach earlier in the article where we had a memo table to cache all our subproblems that were already solved. However, in that approach, the problem was that we were using the recursion stack space. So, let us now optimise that approach and cut down that extra recursive stack space. So, in this approach, we will be using dynamic programming to solve our extra stack space. Let us look at the algorithm.

Algorithm:

• First we create a dp array of size $n+1$, considering $"n"$ to be the length of the given string.
• We initialize the dp array with false. Only, the first index of the dp array is kept as True, since the $null$ string will always be present in the dictionary.
• After that, we also take two index pointers i and j.
• We run a for-loop through i which starts from index 1, and go through the length of the string, i.e. len(s). Inside the loop, we run another loop for j which runs till i.
  • Inside the j loop, we check if the dp[j] is True
  • And if it is True, then we also check if the substring s[i:j] is present in the dictionary or not.
  • If s[i:j] is present, then we simply mark dp[i] as True and break from the loop
• Finally, we return the value present at the $nth$ index of the dp array. If it is True, then yes the wordbreak can be formed, otherwise, no the wordbreak cannot be formed.

Implementation in C++, Java and Python

C++ Implementation

Below given is the C++ code for the above dynamic programming approach.

Code:

Python Implementation

Below given is the Python code for the above dynamic programming approach.

Code:

Output:

Java Implementation

Below given is the Java code for the above dynamic programming approach.

Code:

Time Complexity Analysis

In the above dynamic programming approach, we are iterating through two for-loops which are taking the time of $O(N^2)$, considering $N$ to be the length of the string. Also, at each step, we will be computing the substring of the given string, which will take another $O(N)$. Hence, the worst-case time complexity for this approach will be $O(N^3)$

Space Complexity Analysis

Since we have used a dp array of size N+1, the worst-case space complexity will be $O(N)$.

Approach 5: Using Trie Data Structure

Firstly, let us understand what is a trie data structure.

Tries are a very unique and practical data structure that is built on a string's prefix. Strings are kept in the data structure Trie, and it looks like a graph. There are nodes and edges in it. At most 26 children can be found in each node, and edges join each parent node to its children. These 26 pointers are just pointers for each of the 26 English alphabetic characters. Every edge is kept as a separate edge. It is always a good choice to optimize the search for substrings using a Trie Data Structure.

Explaining the implementation of the Trie data structure is not under the scope of this article. Let us head on to our code for the same.

Algorithm: Here we will only discuss the steps we have performed in the wordBreak recursive function. Implementation of TrieNode is not under the scope of the article.

• First find the length of the string given
• If the length of the string is 0 then return a True because Null character will always be present in the word dictionary given.
• Next, run a loop through the length of the string
• Check if the prefix of the string is present in the Trie or not.
• If the prefix is present, then again run the recursive function through the remaining length of the string.
• Finally return a True if all the prefixes of the string s has been checked and they are present in the word dictionary.

Implementation in C++, Java and Python

C++ Implementation

Below given is the C++ code using the Trie data structure.

Code:

Python Implementation

Below given is the Python code using the Trie data structure.

Code:

Output:

Java Implementation

Below given is the Java code using the Trie data structure.

Code:

Time Complexity Analysis

The Insert and search operation in Trie usually costs $O(keyLength)$. The time complexity for the above operation will be major $O(N^2)$ because we will be performing the search operation inside the for-loop. Please note, N is the length of the string i.e. len(s).

Space Complexity Analysis

The space complexity for the above approach will be $O(N + M)$, where N is the length of the string i.e. len(s) and M is the number of words in the wordDict.