/**
* 140. Word Break II
* Given a non-empty string s and a dictionary wordDict containing a list of non-empty words,
* add spaces in s to construct a sentence where each word is a valid dictionary word. Return all such possible sentences.
* Note:
* The same word in the dictionary may be reused multiple times in the segmentation.
* You may assume the dictionary does not contain duplicate words.
* Example 1:
* Input:
* s = “catsanddog”
* wordDict = [“cat”, “cats”, “and”, “sand”, “dog”]
* Output:
* [
* “cats and dog”,
* “cat sand dog”
* ]
*/
See the solution on github here: https://github.com/zcoderz/leetcode/blob/main/src/main/java/frequent/hard/WordBreak2.java
Observations:
- The question wants us to return all possible combination of words that can form the given sentence
- For each index in the string, we can find a list of words that form a word which starts at some index before the given index and end at that index.
- We can start from the end index and move back to the first index recursively for each word that was recorded as ending at that index.
Algorithm:
- For each index in the array find list of words that begin before the index and end at it. Note down starting indexes of the words in an array.
- Run a dfs starting from the end of string to the first so as to limit the traversal paths.
Here is the dfs based code to find combination of words that form the string:
void processDFS(int offset, String str) {
if (offset == 0) {
wordOut.add(str.strip());
}
ArrayList<Integer> arr = dp[offset];
for (int iStart : arr) {
String strWord = sentence.substring(iStart, offset);
strWord = strWord + " " + str;
processDFS(iStart, strWord);
}
}
Here is the code which constructs per ending index a list of starting indexes for words that end at the given ending index.
public List<String> wordBreak(String s, List<String> wordDict) {
this.sentence = s;
this.len = s.length();
wordSet = new HashSet<>(wordDict);
dp = new ArrayList[len + 1];
Arrays.setAll(dp, ArrayList::new);
HashSet<Character> sentenceChars = new HashSet<>();
updateCharSet(s, sentenceChars);
HashSet<Character> dictChars = new HashSet<>();
for (String word : wordDict) {
updateCharSet(word, dictChars);
}
//this is a quick check to exit early if no matches are possible
boolean contains = dictChars.containsAll(sentenceChars);
if (!contains) return new ArrayList<>();
//for each index in the string create a list that contains
//starting indexes that can map to the given characters
for (int end = 1; end <= len; end++) {
ArrayList<Integer> aList = dp[end];
for (int start = 0; start < end; start++) {
if (wordSet.contains(sentence.substring(start, end))) {
aList.add(start);
}
}
}
wordOut = new ArrayList<>();
//start from the end , while traversing back to start because you limit the traversal paths that way
processDFS(len, "");
return wordOut;
}