Word Break II

LeetCode Q 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" ]
Example 2:
Input: s = "pineapplepenapple", wordDict = ["apple", "pen", "applepen", "pine", "pineapple"] Output: [ "pine apple pen apple", "pineapple pen apple", "pine applepen apple" ]
Explanation: Note that you are allowed to reuse a dictionary word.
Example 3:
Input: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"] Output: []

Solution : Backtracking with memorization

Using DFS directly will lead to TLE, so just use HashMap to save the previous results to prune duplicated branches.

Code:

Map<String, ArrayList<String>> memo;
public List<String> wordBreak(String s, List<String> wordDict) {
	memo = new HashMap<String, ArrayList<String>>();
	return wordBreakHelper(s, wordDict);
}

private List<Strig> wordBreakHelper(String s, List<String> wordDict) {
	if (memo.containsKey(s)) return memo.get(s);

	List<Strig> res = new ArrayList<>();
	if (s == null || s.length() == 0) return res;
	if (wordDict.contains(s)) res.add(s);

	for (int len = 1; len < s.length; i++) {
		String word = s.substring(0, len);
		if (!wordDict.contains(word)) continue;
		List<String> strs = wordBreak(s.substring(len), wordDict);
		for (String str: strs) {
			res.add(word + " " + str);
		}
	}
	
	memo.put(s, res);
	return res;
}