Word Break II
Let's solve the Word Break II problem using Dynamic Programming.
Statement
Given a string s
and a dictionary of strings wordDict
, add spaces to s
to break it up into a sequence of valid words from wordDict
. 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 wordDict
= [“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:
-
s.length
-
wordDict.length
-
wordDict[i].length
-
s
as well as all the strings inwordDict
consist only of lowercase English letters. -
All the strings in
wordDict
are unique.
Examples
Level up your interview prep. Join Educative to access 80+ hands-on prep courses.