Medium
这个图很清楚地表达了递归做这个题的方法：
helper method有两种情况可以直接返回值
- 原字符串就在dictionary里面，这时候可以直接返回true, 但要注意记得往memo里面放结果来实现记忆化搜索
- memo里面有该字符是否在字典里的记录，也就是记忆化搜索的优点，不用重复计算
不懂
//why this following step is necessary???
memo.put(s, true);
return true;
这里为什么还必须写memo.put(s, true),直接返回true不行吗？
image.png
class Solution {
public boolean wordBreak(String s, List<String> wordDict) {
/* leetcode dict:{leet, code}
wordBreak("l") && inDict("eetcode")
wordBreak("le") && inDict("etcode")
wordBreak("lee") && inDict("tcode")
wordBreak("leet") && inDict("code")
*/
Set<String> dict = new HashSet<>(wordDict);
Map<String, Boolean> memo = new HashMap<>();
return wordBreak(s, dict, memo);
}
private boolean wordBreak(String s, Set<String> dict, Map<String, Boolean> memo){
if (dict.contains(s)){
memo.put(s,true);
return true;
}
if (memo.containsKey(s)){
return memo.get(s);
}
for (int i = 1; i < s.length(); i++){
if (wordBreak(s.substring(0, i), dict, memo) && dict.contains(s.substring(i))){
memo.put(s, true);
return true;
} else {
memo.put(s, false);
}
}
return false;
}
}
