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(); } } };
相关推荐
python python_leetcode题解之139_Word_Break
python python_leetcode题解之140_Word_Break_II
javascript js_leetcode题解之139-word-break.js
javascript js_leetcode题解之140-word-break-ii.js
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]...
* Word Break、Word Break II:该题目要求将字符串分割成单词,实现方法使用了动态规划和回溯算法。 * Word Ladder:该题目要求将一个单词转换成另一个单词,实现方法使用了广度优先搜索算法。 二、树和图 * ...
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 = [...
- **Word Break**:判断一个字符串是否可以拆分为一个词汇表中的单词序列。 7. **链表(Linked List)**: - **Linked List Cycle**:检测链表中的环。 - **Remove Duplicates from Sorted List**:从已排序的...
4. Solution Word Break 单词断词是一个自然语言处理问题,要求将字符串断词为单词。可以使用动态规划或Trie树来解决该问题。 5. Word Break II 单词断词II是一个变体的问题,要求将字符串断词为单词,并且可以...
var wordBreak = function(s, wordDict) { let n = s.length; let dp = new Array(n + 1).fill(false); dp[0] = true; for (let i = 0; i ; i++) { for (let j = 0; j ; j++) { if (dp[j] && wordDict....
function wordBreak(s, wordDict) { const dp = Array(s.length + 1).fill(false); dp[0] = true; for (let i = 1; i ; i++) { for (const word of wordDict) { if (s.startsWith(word, i - word.length) && ...
在提供的代码库"WordBreak-Leetcode-139-master"中,你可能会找到一个具体的实现,它可能包括以下部分: - 主函数,接收字符串sentence和词汇表wordDict作为输入参数。 - 动态规划的逻辑,包括初始化dp数组和遍历...
def wordBreak(s, wordDict): wordDict = set(wordDict) # 将单词列表转换为集合,加快查找速度 dp = [False] * (len(s) + 1) # 初始化动态规划数组,dp[i]表示s[:i]是否可以被拆分 dp[0] = True # 空字符串可以...
- **题目描述:**给定两个字符串word1和word2,返回使word1和word2相同所需的最小步数。每步可以插入一个字符、删除一个字符或者替换一个字符。 - **应用场景:**自然语言处理中的拼写纠错、相似度比较等场景。 ...
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.摆