|
LeetCode： 140. 单词拆分 II
解法： 递归回溯
直接递归回溯会出问题， 在 aaaaaaaaaaaaabaaaaaaaaaaaaaa的情况下会出现大量的重复计算。造成超时
使用记忆化递归 >> 降低时间复杂度
用 map 或数组存储计算结果，数组索引为指针位置，值为子调用的结果。下次遇到相同的子问题时，直接返回 memo 中的缓存值，避免进入重复的递归
递归回溯
不知道怎么剪枝 >> 取巧了 >> 规避了 aaaaaaaaaaaaabaaaaaaaaaaa 这种样例 
public List wordBreak(String s, List wordDict) {
if(s == null) return list;
String c = wordDict.toString();
for (int i = 0; i
if(left >= s.length()){
// 一种答案
list.add(ans.substring(0, ans.length() - 1));
return ;
}
for (int i = left; i
// 找到第一个相等的
ans.append(temp).append(" ");
dfs(s, "", i + 1, wd);
// 把当前单词删除
ans.delete(ans.length() - (temp.length() + 1), ans.length());
}
}
}
记忆化搜索降低时间复杂度 >> 官方的 Java 版题解没看懂 
记忆化递归代码
优化
样例： “pineapplepenapple” Arrays.asList(“apple”, “pen”, “applepen”, “pine”, “pineapple”)
public List wordBreak(String s, List wordDict) {
if(s == null) return new ArrayList();
return dfs(s, "", 0, wordDict);
}
Map map = new HashMap();
public List dfs(String s, String temp, int left, List wd){
if(map.containsKey(left)) return map.get(left);
if(left >= s.length()) return new ArrayList(){{add("");}};
List ret = new ArrayList();
for (int i = left; i
List last = dfs(s, "", i + 1, wd);
for (String str: last) {
ret.add(str.equals("")? temp : temp + " " + str);
}
}
}
map.put(left, ret);
return ret;
}
>> 参考dl
|