首页 > 代码库 > 【leetcode】Word Break II (hard)★
【leetcode】Word Break II (hard)★
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"].
思路：
我自己用回溯做超时了，直接看大神的20ms代码吧
主要是即考虑了从前向后的连接，也考虑了从后向前的连接。
class Solution {public: vector<string> wordBreak(string s, unordered_set<string> &dict){ vector<vector<int>> flag(s.size() + 1, vector<int>()); flag[0].push_back(0); for (int i = 1; i <= s.size(); i++) //当前判断字符串的结束位置的下一个位置 如i=1 表示结束位置是 s[0] 从前向后 { for (int j = 0; j < i; j++) //当前判断的字符串的起始位置 { if (!flag[j].empty() && dict.find(s.substr(j, i - j)) != dict.end()) //只有该单词前面的单词能够找到时才压入结果 { flag[i].push_back(j); //flag[i]中存储 以i为结束位置的下一个位置的单词 的起始位置 如flag[2] 里面存储的都是以s[1]结束的单词的第一个字母的位置 } } } vector<string> result; getResult(result, flag, s, s.size()); //从后向前找结果， 只有能够划分到最后一个字母的单词切割方式才考虑 return result;}void getResult(vector<string> &result, vector<vector<int>> &flag, string s, int n){ for (int j = 0; j < flag[n].size(); j++) { int i = flag[n][j]; if (i == 0) //找到起始点了，压入划分的答案 { result.push_back(s); continue; } s.insert(s.begin() + i, ‘ ‘); getResult(result, flag, s, i); s.erase(i, 1); }}};
我自己TLE的代码，我只考虑了从前向后，非常繁琐。但具体为什么会慢那么多我还没想明白。仅仅是因为没有考虑从后向前吗？
class Solution {public: vector<string> wordBreak(string s, unordered_set<string> &dict) { vector<vector<bool>> issubstr(s.size(), vector<bool>(s.size(), false)); for(int i = 0; i < s.size(); i++) { for(int j = 1; j <= s.length() - i; j++) { if((find(dict.begin(), dict.end(), s.substr(i, j))) != dict.end()) { issubstr[i][i + j - 1] = true; } } } vector<string> ans; vector<string> X; vector<vector<string>> S(1); int k = 0; for(int i = 1; i <= s.length(); i++) { if(issubstr[0][i - 1]) { S[k].push_back(s.substr(0, i)); } } while(k >= 0) { while(!S[k].empty()) { while(X.size() > k) { X.pop_back(); } X.push_back(S[k].back()); S[k].pop_back(); int Xtotallen = 0; vector<string>::iterator it; for(it = X.begin(); it != X.end(); it++) { Xtotallen += it->length(); } if(Xtotallen == s.length()) { string partans = X[0]; for(it = X.begin() + 1; it != X.end(); it++) { partans += " "; partans += (*it); } ans.push_back(partans); } else { k++; if(S.size() <= k) { S.push_back(vector<string>()); } for(int i = 1; i <= s.length() - Xtotallen; i++) { if(issubstr[Xtotallen][Xtotallen + i -1]) { S[k].push_back(s.substr(Xtotallen, i)); } } } } k--; } return ans; }};
【leetcode】Word Break II (hard)★
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。