Solution
- 因为要求所有解，所以不能像139一样找到一组解就返回，需要找到所有解。
- 同样需要使用记忆递归：
Map<String, List<String>> 表示该String，能分解且能够在wordList中找到的substring。
- 递归函数，返回List<String> 即为找到的结果
- base case：
当startIndex == endIndex, return null, 代表的情况是 例如 cat， startIndex已经走到了3，cat已经全部扫描完成，其右边不能再继续递归了，所以返回空。
- 再判断
MAP中是否已有记录，如果有，则直接返回记录值
- 如果都不满足，那么开始对当前substring进行处理
class Solution {
public List<String> wordBreak(String s, List<String> wordDict) {
if (wordDict == null || wordDict.size () == 0) {
return new ArrayList<String> ();
}
Map<String, List<String>> tracker = new HashMap<> ();
Set<String> wordSet = new HashSet<> (wordDict);
return wordBreakHelper (s, wordSet, 0, s.length (), tracker);
}
private List<String> wordBreakHelper (String str,
Set<String> wordDict,
int start,
int end,
Map<String, List<String>> tracker) {
if (tracker.containsKey (str.substring (start, end)))
return tracker.get (str.substring (start, end));
// base case: if it is a null string, return null
if (start == end)
return null;
List<String> result = new ArrayList<> ();
for (int i = start; i < end; i++) {
String subTemp = str.substring (start, i + 1);
List<String> partialResult = new ArrayList<> ();
if (wordDict.contains (subTemp)) {
System.out.println ("--- contains: " + subTemp);
partialResult = wordBreakHelper (str, wordDict, i + 1, end, tracker);
// partial result == null 对应的是已经全部走完了，cat，startIndex已经走到了t后面，相当于找到整个cat，所以将其放入result
if (partialResult == null) {
result.add (subTemp);
System.out.println (subTemp + ": add to result");
} else {
// 不为null的时候，那么就把subTemp与所有的partialResult进行组合，就是解
for (String subTempNext : partialResult) {
result.add (subTemp + " " + subTempNext);
System.out.println ("------" + subTemp + " " + subTempNext);
}
}
}
}
tracker.put (str.substring (start, end), result);
return result;
}
}
