原题链接:http://oj.leetcode.com/problems/word-break-ii/这道题目要求跟Word
Break比较类似,不过返回的结果不仅要知道能不能break,如果可以还要返回所有合法结果。一般来说这种要求会让动态规划的效果减弱很多,因为我们要在过程中记录下所有的合法结果,中间的操作会使得算法的复杂度不再是动态规划的两层循环,因为每次迭代中还需要不是constant的操作,最终复杂度会主要取决于结果的数量,而且还会占用大量的空间,因为不仅要保存最终结果,包括中间的合法结果也要一一保存,否则后面需要历史信息会取不到。所以这道题目我们介绍两种方法,一种是直接brute
force用递归解,另一种是跟Word
Break思路类似的动态规划。对于brute force解法,代码比较简单,每次维护一个当前结果集,然后遍历剩下的所有子串,如果子串在字典中出现,则保存一下结果,并放入下一层递归剩下的字符。思路接近于我们在N-Queens这些NP问题中经常用到的套路。代码如下:public ArrayList<String> wordBreak(String s, Set<String> dict) {
ArrayList<String> res = new ArrayList<String>();
if(s==null || s.length()==0)
return res;
helper(s,dict,0,"",res);
return res;
}
private void helper(String s, Set<String> dict, int start, String item, ArrayList<String> res)
{
if(start>=s.length())
{
res.add(item);
return;
}
StringBuilder str = new StringBuilder();
for(int i=start;i<s.length();i++)
{
str.append(s.charAt(i));
if(dict.contains(str.toString()))
{
String newItem = item.length()>0?(item+" "+str.toString()):str.toString();
helper(s,dict,i+1,newItem,res);
}
}
}
接下来我们列出动态规划的解法,递推式跟Word
Break是一样的,只是现在不只要保存true或者false,还需要保存true的时候所有合法的组合,以便在未来需要的时候可以得到。不过为了实现这点,代码量就增大很多,需要一个数据结构来进行存储,同时空间复杂度变得非常高,因为所有中间组合都要一直保存。时间上还是有提高的,就是当我们需要前面到某一个元素前的所有合法组合时,我们不需要重新计算了。不过最终复杂度还是主要取决于结果的数量。代码如下:class Interval {
int start;
int end;
public Interval(int start, int end) {
this.start = start; this.end = end;
}
public Interval(Interval i) {
start = i.start;
end = i.end;
}
}
ArrayList<ArrayList<Interval>> deepCopy(ArrayList<ArrayList<Interval>> paths) {
if (paths==null) return null;
ArrayList<ArrayList<Interval>> res = new ArrayList<ArrayList<Interval>>(paths.size());
for (int i=0; i<paths.size(); i++) {
ArrayList<Interval> path = paths.get(i);
ArrayList<Interval> copy = new ArrayList<Interval>(path.size());
for (int j=0; j<path.size(); j++) {
copy.add(new Interval(path.get(j)));
}
res.add(copy);
}
return res;
}
public ArrayList<String> wordBreak(String s, Set<String> dict) {
ArrayList<String> res = new ArrayList<String>();
if (s==null || s.length()==0) return res;
Map<Integer, ArrayList<ArrayList<Interval>>> dp = new HashMap<Integer, ArrayList<ArrayList<Interval>>>();
dp.put(0, new ArrayList<ArrayList<Interval>>());
dp.get(0).add(new ArrayList<Interval>());
for (int i=1; i<=s.length(); i++) {
for (int j=0; j<i; j++) {
String cur = s.substring(j, i);
ArrayList<ArrayList<Interval>> paths = null;
if (dp.containsKey(j) && dict.contains(cur)) {
paths = deepCopy(dp.get(j));
Interval interval = new Interval(j, i);
for (ArrayList<Interval> path:paths) {
path.add(interval);
}
}
if (paths != null) {
if (!dp.containsKey(i)) {
dp.put(i, paths);
}
else {
dp.get(i).addAll(paths);
}
}
}
}
if (!dp.containsKey(s.length())) {
return res;
}
ArrayList<ArrayList<Interval>> paths = dp.get(s.length());
for (int j=0; j<paths.size(); j++) {
ArrayList<Interval> path = paths.get(j);
StringBuilder str = new StringBuilder();
for (int i=0; i<path.size(); i++) {
if (i!=0) {str.append(" ");}
int start = path.get(i).start;
int end = path.get(i).end;
str.append(s.substring(start, end));
}
res.add(str.toString());
}
return res;
}
可以看出,用动态规划的代码复杂度要远远高于brute
force的解法,而且本质来说并没有很大的提高,甚至空间上还是一个暴涨的情况。所以这道题来说并不是一定要用动态规划,有一个朋友在面Amazon时遇到这道题,面试官并没有要求动态规划,用brute force即可,不过两种方法时间上和空间上的优劣还是想清楚比较好,面试官可能想听听理解。实现的话可能主要是递归解法。还有一点需要指出的是,上面的两个代码放到LeetCode中都会超时,原因是LeetCode中有一个非常tricky的测试case,其实是不能break的,但是又很长,出现大量的记录和回溯,因此一般通过这个的解法是把Word
Break先跑一遍,判断是不是能break,如果可以再跑上面的代码。这样做法其实比较傻,但是为了过这个只能这样了,这一点我觉得LeetCode没必要把超时设得这么严格,实际意义不大,只是把AC率给拉了下来哈。
分享到:
相关推荐
Algorithm-LeetCode-Sol-Res.zip,干净,易懂的解决方案和资源,为leetcode在线判断算法问题。,算法是为计算机程序高效、彻底地完成任务而创建的一组详细的准则。
Article-Views-II-LeetCode.png 平均工资-部门-VS-公司-LeetCode.png 平均销售价格-LeetCode.png 每台机器平均处理时间 LeetCode.png Bank-Account-Summary-II-LeetCode.png Bank-Account-Summary-LeetCode.png 大国...
Algorithm-leetcode-spider.zip,leetcode公司,算法是为计算机程序高效、彻底地完成任务而创建的一组详细的准则。
~/.vscode/extensions/leetcode.vscode-leetcode-0.17.0/node_modules/vsc-leetcode-cli/bin/leetcode /usr/local/bin/leetcode 修改模板 open ~/.vscode/extensions/leetcode.vscode-leetcode-0.17.0/node_modules/...
leetcode-cli-plugins leetcode-cli 的第 3 方插件。 什么是 如何使用 如何使用 插件 名称 描述 增强的命令 按公司或标签过滤问题 list 不要在同一台计算机上使 Chrome 的会话过期 login 不要在同一台计算机上使 ...
锈cauly-rust-leetcode-utils 这个项目为用 rust 语言编写 leetcode 提供了一些帮助。 如何使用 方法一: [Folk and] 克隆这个 repo。 在你的 leetcode cargo.toml 中,添加: [dependencies] cauly-rust-leetcode-...
Algorithm-LeetCode-Solution-From-GuaZiDou.zip,Leetcode解决方案Gitbook,算法是为计算机程序高效、彻底地完成任务而创建的一组详细的准则。
Swif-LeetCode-Utils:在LeetCode上快速创建和打印ListNode和TreeNode的方式
断字leetcode WordBreak-Leetcode-139 Leetcode 问题 139(中) 问题中使用的技术:动态规划
《leetcode-solutions》,刷算法题,需要有一定的英文阅读能力。。。
RandomPickWithWeight-LeetCode-528-源码.rar
Java-Leetcode-杨辉三角
leetcode-cheat 的发布 它是什么 ? 这是一个chrome 扩展,可以帮助您更高效地使用 leetcode。您可以从 重要: leetcode-cheat 现在只支持中文版。 也就是说不完全支持leetcode.com,但是你可以用leetcode-cn.com代替...
前端大厂最新面试题-leetcode-interview-ts.docx
解题思路思路和LeetCode-python 503.下一个更大元素 II一致,只是这里求的是下标的距离,而不是数值倒序搜索,用到栈,栈里存储索引情况1:若栈为
leetcode-cli 注意:这个存储库是为了临时使用而分叉的。 注意:从 webbrowser 复制 cookie 并使用leetcode user -c可以临时修复不能。 一个享受 leetcode 的高效 cli 工具! 非常感谢 leetcode.com,一个非常棒的...
leetcode 答案Leetcode---数据库 我对 Leetcode 数据库问题的回答
Algorithm-LeetCode-NOTES.zip,利特码,算法是为计算机程序高效、彻底地完成任务而创建的一组详细的准则。
lru缓存leetcode Go 中解决的一些 Leetcode 问题 大批 3sum-0015 买卖股票的最佳时机-0121 最多水的容器-0011 contains-duplicate-0217 find-minimum-in-rotated-sorted-array-0153 ...word-break-0139 图形
leetcode 答案 -leetcode- leetcode刷题指南 不只是答案 更多的是过程 更重要的是纠错的过程