DP - Word Break

Given a string s and a dictionary of strings wordDict, return true if s can be segmented into a space-separated sequence of one or more dictionary words. note that the same word in the dictionary may be reused multiple times in the segmentation.

Input: s = "codecs", wordDict = ["cs","code"]
Output: true
Explanation: "codecs" can be made using the words from dictionary.

Input: s = "applepenapple", wordDict = ["apple","pen"]
Output: true
Explanation: "applepenapple" can be made using "apple" and "pen" words from dictions and we have to use "pen" word two times and we are allowed to use as per problem statement.

Input: s = s = "catsandog", wordDict = ["cats","dog","sand","and","cat"]
Output: false
Explanation:"catsandog" cannot be made using the words from dictionary.

Solution 1 - using brute force approach
Solution 2 - using DP memoization
Solution 3 - using DP Bottom-Up approach using tabulation and memory optimized

In this approach, we will start with every word from wordDict and check if the input string s is starting with that word or not, if it is continue this process with remainder substring.

Say for example if the input string given is "cscode" and word dictionary is {"code", "cs"}

We start with 1^st word "code" from dictionary, and "cscode" is not starting with this word, so we stop exploring this path.
Then we start with 2^nd word "cs" from dictionary, and "cscode" starts with this word, so we continue to explore this path. Since the input string starts with word "cs", we take the remainder string "code" and continue this process.
- Again we start with 1^st word "code" from dictionary, and remainder substring "code" starts with this letter, so we can return true from step.

If we look at the decision tree for all possible combinations, it will look like below diagram.

We will create a function bruteForceApproach that takes input target string s and array of strings wordDict.
Base cases are:
- If the input string's length is 0, return true, because when we are recursively calling the function, substrings length will become 0 only if we can make up the target string using the words from wordDict.
For every word in wordDict, check if the the target string s starts with that word or not.
- If the target string starts with the word, then take the remainder substring and call bruteForceApproach recursively.
- If the target string doesn't start with the word, return false.

public class WordBreak { /* brute force approach*/ static boolean bruteForceApproach(String s, String[] wordDict) { if(s.length()==0){ return true; } for(String word: wordDict) { if(s.indexOf(word) == 0) { // if the string starts with the word String remainder = s.substring(word.length()); if(bruteForceApproach(remainder, wordDict)) { return true; // possible to construct the string using words from wordDict } } } return false; } }

Complexity Analysis:

Time complexity: Above code runs in O(n^m * m) time where n is the length of wordDict array and m is the length of the input target string s this is because whenever we found a match of starting word from dictionary, we are recursively calling the function for the remainder string and again for every match we are repeating the process.
The height of the decision will be m and for at each possible remainder we are making n calls to check every word from dictionary, that is O(n^m) and the other m is because of the substring operation.
Space complexity: O(m²) since we calling the function recursively, this is memory used for remainder substring and number of recursive calls in the stack.

In the above implementation, we have created substrings using the indexes for easiness of understanding, but when we call the function recursively we could also pass starting index as parameter and avoid creating substrings, in that case space complexity will be O(n^m).

From the above brute force approach, we can notice that there are some overlapping problems. For example, consider target s = "abcdxyz" and wordDict = {"abc", "d", "abcd", "lion"}

If we construct a decision tree to see the possibilities whether the string can be made using the dictionary of words , it looks like below diagram and as you can see highlighted sub problems are overlapping.
So, in this approach, we will be caching sub problem result into a HashMap with input string as key and its result as value. When a sub problem is repeated and found in cache, we will return it, otherwise we will call the function recursively and cache its result.

import java.util.HashMap; public class WordBreak { /* DP memoization approach */ static boolean dpMemoizationApproach(String s, String[] wordDict) { HashMap<String, Boolean> cache = new HashMap<>(); return dpMemoizationApproachRec(s, wordDict, cache); } static boolean dpMemoizationApproachRec(String s, String[] wordDict, HashMap<String, Boolean> cache) { if(s.length() == 0) { return true; } if(cache.containsKey(s)) { return cache.get(s); } for( String word: wordDict) { if(s.indexOf(word) == 0) { String remainder = s.substring(word.length()); if (dpMemoizationApproachRec(remainder, wordDict, cache)) { cache.put(remainder, true); return true; } } } cache.put(s, false); return false; } }

Complexity Analysis:

Time complexity: Above code runs in O(n * m²) time where n is the length of wordDict array and m is the length of the input target string s. This is because, for every word in dictionary, we are checking if this is a suffix or not (n * m), then creating a substring if it is a suffix (m).
Space complexity: O(m²) for the cache we are maintaining (m) , stack for recursive calls and the substring operation (m * m).

In this approach we will look at solving the problem using dynamic programming using tabulation caching mechanism.

In this solution, we are going to create a temporary array with size as m + 1, where m is target string length and +1 is to store value at the right end of cache array for base case. In this cache array, we are going to store whether a substring ending index i exists in the words dictionary or not.

To start with, at the right end of cache, we will store true, this is the base case, if we reach end of array that means target string s can be made up using the words from wordDict.
Then, for each letter from right to left, check if that substring exists in the wordDict if it exists, then copy cache value from end index of the substring. cache[i] = cache [i + length(word)]; The reason we do that is because, consider this example s = "abcd" and wordDict = {"ab", "cd"}
- We start with cache as [false, false, false, false, true]
- When i= 3, neither of words "ab" or "cd" can fit from this index.
- When i= 2, word "cd" can fit from this index. So, we update the cache: cache[3] = cache[3 + length("cd")]; = cache[3+2]; = cache[5]; Now, the cache becomes [false, false, true, false, true]. This means that there is a bridge from current substring and from the ending index of current substring.
- When i= 1, neither of words "ab" or "cd" can fit from this index.
- When i= 0, word "ab" can fit from this index. So, we update the cache: cache[0] = cache[0 + length("ab")]; = cache[2]; Now, the cache becomes [true, false, true, false, true]. This means that there is a bridge from current substring "ab" and from the ending index of current substring "ab" which is "cd".
- Finally we will return the value at 0^th index. So, our answer will be true.

public class WordBreak { /* DP tabulation memory optimized */ static boolean dpTabulationMemoryOptimized(String s, String[] wordDict) { boolean[] cache = new boolean[s.length()+1]; cache[s.length()] = true; // if we reach the end of input target string, that means string "s" // can be constructed using words from wordDict. for (int i=s.length()-1; i>=0; i--) { for(String word : wordDict) { if(i+ word.length() <= s.length() && word.equals(s.substring(i, i+word.length()))) { // i+ word.length() <= s.length() => // to check if "s" has enough characters to check cache[i] = cache[i + word.length()]; } if(cache[i] == true) { // we have found a matching word break; } } } return cache[0]; } }

Complexity Analysis:

Time complexity: Above code runs in O(n * m²) time where n is the length of wordDict array and m is the length of the input target string s. This is because, for every word in dictionary, we are checking if this is a suffix or not (n * m), then creating a substring if it is a suffix (m).
Space complexity: O(m) for the cache we are maintaining that is of input string length.

Above implementations source code can be found at GitHub link for Java code

Contents

Complexity Analysis:

Complexity Analysis:

Complexity Analysis: