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.
For example, given
s = "leetcode"
,
dict = ["leet", "code"]
.
Return true because "leetcode"
can be segmented as "leet code"
.
建字典树搞。
class Solution { public: class Node { public: Node* next[26]; bool end; Node(): end(false) { for (int i = 0; i < 26; i++) next[i] = NULL;} void insert(string a) { Node * cur = this; for (int i = 0; i < a.size(); i++) { if (cur->next[a[i]-'a'] == NULL) { cur->next[a[i]-'a'] = new Node(); } cur = cur->next[a[i]-'a']; } cur->end = true; } ~Node () { for (int i = 0;i < 26; i++) delete next[i]; } }; bool wordBreak(string s, unordered_set<string> &dict) { Node root; for (auto it = dict.begin(); it != dict.end(); ++it) { root.insert(*it); } vector<bool> v(s.size(), false); findMatch(s, &root, 0, v); for (int i = 0; i < s.size(); i++) if (v[i]) findMatch(s, &root, i+1, v); return v[s.size() - 1]; } void findMatch(const string& s, Node* cur, int start, vector<bool> &v) { int i = start, n = s.size(); while (i < n) { if (cur->next[s[i] - 'a'] != NULL) { if (cur->next[s[i] - 'a']->end) v[i] = true; cur = cur->next[s[i] - 'a']; } else break; i++; } } };
粗暴一点也是ok的。
class Solution { public: bool wordBreak(string s, unordered_set<string> &dict) { int n = dict.size(); int maxlen = 0; for (auto it = dict.begin(); it != dict.end(); ++it) if (it->size() > maxlen) maxlen = it->size(); int sn = s.size(); vector<bool> v(sn, false); for (int i = 0; i < sn; i++) { if (i == 0 || (i > 0 && v[i-1])) { for (int j = 1; j <= maxlen && i + j - 1 < sn; j++) { if (dict.count(s.substr(i,j)) > 0) v[i+j-1] = true; } } } return v[sn-1]; } };
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.
For example, given
s = "catsanddog"
,
dict = ["cat", "cats", "and", "sand", "dog"]
.
A solution is ["cats and dog", "cat sand dog"]
.
class Solution { public: vector<string> wordBreak(string s, unordered_set<string> &dict) { vector<string> res; int dn = dict.size(); int sn = s.size(); int maxlen = 0; for (auto it = dict.begin(); it != dict.end(); ++it) { if (it->size() > maxlen) maxlen = it->size(); } vector<vector<int> > next(sn); vector<bool> v(sn, false); for (int i = 0; i < sn; i++) { if (i == 0 || (i > 0 && v[i-1])) { for (int j = 1; j <= maxlen && i+j-1 < sn; j++) { if (dict.count(s.substr(i, j)) > 0) { v[i+j-1] = true; next[i].push_back(j); } } } } if (!v[sn-1]) return res; vector<int> x; x.push_back(0); gen(s, res, next, x); return res; } void gen(const string& s, vector<string>& res, vector<vector<int> >& next, vector<int> &v) { int cur = v.back(); if (cur == s.size()) { string t = s.substr(v[0], v[1] - v[0]); for (int i = 1; i < v.size() - 1; i++) t += " " + s.substr(v[i], v[i+1] - v[i]); res.push_back(t); return; } for (int i = 0; i < next[cur].size(); i++) { v.push_back(cur+next[cur][i]); gen(s, res, next, v); v.pop_back(); } } };
相关推荐
15 | [3 Sum](https://leetcode.com/problems/3sum/) | [C++](./C++/3sum.cpp) [Python](./Python/3sum.py) | _O(n^2)_ | _O(1)_ | Medium || Two Pointers 16 | [3 Sum Closest]...
断字leetcode WordBreak-Leetcode-139 Leetcode 问题 139(中) 问题中使用的技术:动态规划
1: Input: s = "leetcode", wordDict = ["leet", "code"] Output: true Explanation: Return true because "leetcode" can be segmented as "leet code". Example 2: Input: s = "applepenapple", wordDict = [...
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 530 力扣在线评委 # 问题 困难 解决方案 1 简单的 2 中等的 3 中等的 12 中等的 22 中等的 39 中等的 94 中等的 108 中等的 122 中等的 136 中等的 144 中等的 167 中等的 238 中等的 260 中等的 268 中等...
Break](Leetcode 问题/数组和字符串/139.word_break.md) [140. Word Break ii](Leetcode 问题/数组和字符串/140.word_break_ii.md) [151. 反转字符串中的单词](Leetcode Problems/Array and String/151.reverse_...
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 【演示记录】 报告 展示 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 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 ...