This page explains Java solution to problem Word Break II
using Recursion with memoization
.
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:
Example 2:Input: s = "catsanddog", wordDict = ["cat", "cats", "and", "sand", "dog"]
Output:
[
"cats and dog",
"cat sand dog"
]
Input: s = "pineapplepenapple", wordDict = ["apple", "pen", "applepen", "pine", "pineapple"]
Output:
[
"pine apple pen apple",
"pineapple pen apple",
"pine applepen apple"
]
package com.vc.hard;
import java.util.*;
class WordBreakIi {
private HashMap<Integer, List<String>> memo = new HashMap<>();
public List<String> wordBreak(String s, List<String> wordDict) {
HashSet<String> words = new HashSet<>(wordDict);
memo.put(s.length(), Collections.singletonList(""));
return helper(s, 0, words);
}
private List<String> helper(String s, int from, HashSet<String> words) {
if(memo.containsKey(from)) return memo.get(from);
List<String> subRes = new ArrayList<>();
for(int len = 1; from + len <= s.length(); len++) {
String prefix = s.substring(from, from + len);
if(words.contains(prefix)) {
List<String> remaining = helper(s, from + len, words);
for(String remainingStr: remaining) {
String output = remainingStr.length() > 0 ? prefix + " " + remainingStr : prefix;
subRes.add(output);
}
}
}
memo.put(from, subRes);
return subRes;
}
}
O(N! + W) Where
N is total number of elements in an input String s.
W is total number of elements in an input array wordDict.
O(W + 2N) Where
N is total number of elements in an input String s.
W is total number of elements in an input array wordDict.