Word Break II

Let's solve the Word Break II problem using Dynamic Programming.

Statement

Given a string s and a dictionary of strings word_dict, add spaces to s to break it up into a sequence of valid words from word_dict. We are required to return all possible sequences of words (sentences). The order in which the sentences are listed is not significant.

Note: The same dictionary word may be reused multiple times in the segmentation.

Let’s say we have a string s = “catsanddog” and the word dictionary word_dict = [“cat”, “and”, “cats”, “dog”]. Of all the possible sentences that may be formed, consider the sentence “cats and dog”. These are the words in our sentence:

  • “cats”
  • “and”
  • “dog”

and they are all present in the given dictionary.

We can break up s to form a different sentence, e.g., “cat sand dog”, but “sand” is not a word in our dictionary so we cannot consider this sentence as a valid sentence.

Constraints:

  • 11 \leq s.length 60\leq 60

  • 11 \leq word_dict.length 1000\leq 1000

  • 11 \leq word_dict[i].length 60\leq 60

  • s as well as all the strings in word_dict consist only of lowercase English letters.

  • All the strings in word_dict are unique.

Examples

No.

s

word_dict

Output

1

"catsanddog"

["cat", "and", "cats" , "sand", "dog"]

["cats and dog", "cat sand dog"]

2

"catsandog"

["cat", "and", "cats" , "sand", "dog"]

[ ]


3


"pineapplepenapple"


["apple", "pen", "applepen", "pine", "pineapple"]

["pine apple pen apple",

"pineapple pen apple",

"pine applepen apple"]

Try it yourself

Implement your solution in the following playground:

Press + to interact
Python
usercode > main.py
def word_break(s, word_dict):
# Your code will replace the placeholder return statement.
return []
Word Break II

Solution

We will first explore the naive recursive solution to this problem and then see how it can be improved using the Longest Common Substring dynamic programming pattern.

Naive approach

The naive approach to solve this problem is to use a traditional recursive strategy in which we take each prefix of the query string s, and compare it to each word in the dictionary. If it matches, we take the string’s suffix and repeat the process.

Following are the steps to implement the algorithm:

...
Access this course and 1400+ top-rated courses and projects.