Dynamic Programming - Word Break
All diagrams presented herein are original creations, meticulously designed to enhance comprehension and recall. Crafting these aids required considerable effort, and I kindly request attribution if this content is reused elsewhere.
Difficulty : Easy
DP
Problem
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.
Example 1:
1
2
3
Input: s = "leetcode", wordDict = ["leet","code"]
Output: true
Explanation: Return true because "leetcode" can be segmented as "leet code".
Example 2:
1
2
3
4
Input: s = "applepenapple", wordDict = ["apple","pen"]
Output: true
Explanation: Return true because "applepenapple" can be segmented as "apple pen apple".
Note that you are allowed to reuse a dictionary word.
Example 3:
1
2
Input: s = "catsandog", wordDict = ["cats","dog","sand","and","cat"]
Output: false
Solution
DFS Solution
The DFS Solution works really well as we will be moving forward from left to right only when we find a matching word in wordDict
. We can use memorization using a map which would make this as fast as dynamic programming. Let’s follow the template 2 that we have already discussed here.
Define the cache for memorization using map. Then define the dfs()
function which takes truncated s
.
1
2
3
4
cache={}
def dfs(s):
...
Let’s skip the base condition and focus on the actual algorithm first. Since we are using Template 2, we need to have a loop such that we are able to construct words using all the remaining letters as needed. We will start the loop from 1
so that we can keep increasing the window.
1
for index in range(1, len(s)):
Now keep increasing the window
by 1
and each time validate to see its there in wordDict
, if there is match we will call dfs()
again using remaining_s
to repeat this again.
1
2
3
4
5
for index in range(1, len(s)):
window = s[:i]
remaining_s = s[i:]
if window in wordDict and dfs(remaining_s):
...
If the dfs()
inside if
returns True
then there is a solution for remaining_s
, so add remaining_s
in cache
. Now, we do not have to iterate through the for
loop as we know we have a match, hence we will return True
1
2
3
4
if window in wordDict and dfs(remaining_s):
cache[remaining_s]=True
return True
At the end of for
loop if the function has not returned then we know there is no solution for current s
, so lets set that to the cache
as False
and return False
.
1
2
cache[s]=False
return False
Finally, call the dfs()
by passing s
and return its return.
1
return dfs(s)
Now, it’s time to implement the base condition. If at anytime we have the final word then the current s
will always be equal to one of the word present in wordDict
. This will be the terminating condition.
1
2
3
def dfs(s):
if s in wordDict:
return True
Next, if we already have found a solution for s
then just return that as well. If could be either True
or False
.
1
2
if s in cache:
return cache[s]
Dynamic Programming Solution
- Loop backward, all the
True
(matched words) needs to the connected. - Fill each position in DP (Cache) using the previous discovered position. If the previous position is False then the current word is not useful. DP of that position will also be False.
- The bold line indicates success. Not all True values contribute to this.
Here is an example. At the bottom is the cache (DP). Initially all elements are set to False
. Then have 2 loops to match each word at every index location and update DP (Cache) based one the previous ending value.
Here is another example where the output is False
.
Let’s start by defining the dp
cache array. The length of this needs to be 1+len(s)
as we need to start using True
at the end to move forward. This is going to be our base condition.
1
2
dp = [False] * (len(s)+1)
dp[-1] = True
Now we need to loop through s
from backward and then try to match each word. If we have iterated enough to be equal or less then the length the current word in wordDict
then only we can run the comparison.
1
2
3
4
5
for i in range(len(s)-1,-1,-1):
for w in wordDict:
if i+len(w) <=len(s):
if s[i:i+len(w)]==w:
dp[i]=dp[i+len(w)]
If there is at least one match then we don’t have to continue looking for more words.
1
2
if dp[i]:
break
Finally, return the output stored in dp[0]
.
Final Code
Here is the full code.
DFS Solution
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def word_break(s, wordDict):
cache={}
def dfs(s):
if s in wordDict:
return True
if s in cache:
return cache[s]
for index in range(1, len(s)):
window = s[:i]
remaining_s = s[i:]
if window in wordDict and dfs(remaining_s):
cache[remaining_s]=True
return True
cache[s]=False
return False
return dfs(s)
Dynamic Programming Solution
1
2
3
4
5
6
7
8
9
10
11
12
13
def word_break(s, wordDict):
dp = [False] * (len(s)+1)
dp[-1] = True
for i in range(len(s)-1,-1,-1):
for w in wordDict:
if i+len(w) <=len(s):
if s[i:i+len(w)]==w:
dp[i]=dp[i+len(w)]
if dp[i]:
break
return dp[0]