Word Break II
Given a stringsand a dictionary of wordsdict, add spaces insto construct a sentence where each word is a valid dictionary word.
Return all such possible sentences.
For example, given
s="catsanddog"
,
dict=["cat", "cats", "and", "sand", "dog"]
.
A solution is["cats and dog", "cat sand dog"]
.
难度是5星级了。
难度指数直逼word ladder II了
主要的难点: 要优化到极致,不能直接使用递归回溯法,否则超时。
本程序方法:
1 使用二维表vector<vector<int> >tbl记录,记录从i点,能否跳到下一个break位置。如果不能,那么tbl[i]就为空。如果可以,就记录可以跳到哪些位置。
2 利用二维表优化递归回溯法。
优化点:
如果当前位置是start,但是tbl[start]为空,那么就是说,这个break位置不能break整个s串的,直接返回上一层,不用搜索到下一层了。
这样的优化结果是:
如果遇到大数据如:
Input: "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab", ["a","aa","aaa","aaaa","aaaaa","aaaaaa","aaaaaaa","aaaaaaaa","aaaaaaaaa","aaaaaaaaaa"]
Expected: []
输出结果是空,那么使用本程序,运行时间,只是构建动态规划法表使用了O(n*n)时间复杂度(实际运行是O(n)),递归回溯的时候时间是O(1),就可以返回结果了。
这也是本题的考查重点:很多大数据的例子都是返回[]空结果。
当然,如果知道出题者是这样来考我们的,那么我们可以直接排除这种情况,也是可以过的。那么难度指数就会直降至3到4星级了。
本程序是连打带消地对付了这种情况效率是十分高的了,有12ms运行时间的战果。
比网上很多博客的程序要优化,关键是动态规划表的构建功力,本程序的构建方法应该是最优的。有能改进的欢迎指教。
class Solution {
public:
//2014-2-19 update
vector<string> wordBreak(string s, unordered_set<string> &dict)
{
vector<string> rs;
string tmp;
vector<vector<int> > tbl = genTable(s, dict);
word(rs, tmp, s, tbl, dict);
return rs;
}
void word(vector<string> &rs, string &tmp, string &s, vector<vector<int> > &tbl,
unordered_set<string> &dict, int start=0)
{
if (start == s.length())
{
rs.push_back(tmp);
return;
}
for (int i = 0; i < tbl[start].size(); i++)
{
string t = s.substr(start, tbl[start][i]-start+1);
if (!tmp.empty()) tmp.push_back(' ');
tmp.append(t);
word(rs, tmp, s, tbl, dict, tbl[start][i]+1);
while (!tmp.empty() && tmp.back() != ' ') tmp.pop_back();//tmp.empty()
if (!tmp.empty()) tmp.pop_back();
}
}
vector<vector<int> > genTable(string &s, unordered_set<string> &dict)
{
int n = s.length();
vector<vector<int> > tbl(n);
for (int i = n - 1; i >= 0; i--)
{
if(dict.count(s.substr(i))) tbl[i].push_back(n-1);
}
for (int i = n - 2; i >= 0; i--)
{
if (!tbl[i+1].empty())//if we can break i->n
{
for (int j = i, d = 1; j >= 0 ; j--, d++)
{
if (dict.count(s.substr(j, d))) tbl[j].push_back(i);
}
}
}
return tbl;
}
};
分享到:
相关推荐
断字leetcode WordBreak-Leetcode-139 Leetcode 问题 139(中) 问题中使用的技术:动态规划
318| [Maximum Product of Word Lengths](https://leetcode.com/problems/maximum-product-of-word-lengths/) | [C++](./C++/maximum-product-of-word-lengths.cpp) [Python](./Python/maximum-product-of-word-...
Word Break II Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid dictionary word. Return all such possible sentences. Example Example 1...
leetcode 苹果断字 给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict,确定 s 是否可以被分割成一个或多个字典单词的空格分隔序列。 笔记: 字典中的同一个词可能会在切分中重复使用多次。...word. E
第 338 章概括 [(雅虎)4。...问题/数组和字符串/140.word_break_ii.md) [151. 反转字符串中的单词](Leetcode Problems/Array and String/151.reverse_words_in_a_string.md) [167. Two Sum 2 - In
preorder-traversal链表reorder-list链表linked-list-cycle-ii链表linked-list-cycle动态规划word-break-ii动态规划word-break链表copy-list-with-random-pointer复杂度single-number-ii复杂度single-number动态规划
leetcode 【演示记录】 报告 展示 2017/03/06 1.二和,167.二和二 2107/03/06 15.3 总和,16.3 总和最近,18.4 总和,11.最多水的容器 2017/03/09 62.Unique Paths, 63.Unique Paths II, 64.Minimum Path Sum 2017/...
leetcode 530 力扣在线评委 # 问题 困难 解决方案 1 简单的 2 中等的 3 中等的 12 中等的 22 中等的 39 中等的 94 中等的 108 中等的 122 中等的 136 中等的 144 中等的 167 中等的 238 中等的 260 中等的 268 中等...
扩展矩阵leetcode Leetcode Leetcode Answer-Java 数组 11.乘最多水容器 ...wordBreak 279.完全平方数 numSquares 排序 56.合并区间 merge 75.颜色分类 sortColors 179.最大数 largestNumber 324.摆
lru缓存leetcode Go 中解决的一些 Leetcode 问题 大批 3sum-0015 买卖股票的最佳时机-0121 最多水的容器-0011 contains-duplicate-0217 find-minimum-in-rotated-sorted-array-0153 ...word-break-0139 图形
断字leetcode 断字 “断字”问题的解决方案。 用 C# 编写 Given a string s and a dictionary of words dict, determine if s can be segmented into a space-separated sequence of one or more dictionary words. ...
Word Break II Dungeon Game House Robber House Robber II House Robber III Range Sum Query - Immutable Range Sum Query 2D - Immutable 图 Clone Graph 位操作 Reverse Bits Repeated DNA Sequences Number of ...
动态编程递归无重复每个子问题只能评估一次天真的递归方法由于重复而花费指数时间自上而下的回忆这是递归的深度优先搜索实现缓存重复工作自下而上基于依赖图将递归转换为依赖图它是有向无环图您可以使用拓扑排序对......