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 -
sas well as all the strings inwordDictconsist only of lowercase English letters. -
All the strings in
wordDictare unique.
Examples
No. | s | wordDict | 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:
import java.util.*;public class Main {public static List<String> wordBreak(String s, List<String> wordDict) {// Write your code herereturn new ArrayList<String> ();}}
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 ...