首页 > 代码库 > leetcode[140] Word Break II
leetcode[140] Word Break II
这题是上一题的加强版，这里需要返回的是所有可能的分割词。例如：
s = "catsanddog",
dict = ["cat", "cats", "and", "sand", "dog"].
A solution is ["cats and dog", "cat sand dog"].
先用dp求得每个起点到终点是否符合word break 1中的条件，然后利用DFS来递归求解答案。需要注意的是，为了递归的方便，要注意dp要多一个dp[s.size() + 1]长度
class Solution {public: //140 void dfs140(string s, unordered_set<string> &dict, vector<string> &ans, vector<string> &vec, bool dp[], int start) { if (start == s.size()) { if (vec.size() > 0) { string str = vec[0]; for (int i = 1; i < vec.size(); i++) { str = str + " " + vec[i]; } ans.push_back(str); } return ; } for (int i = 1; i <= s.size() - start; i++) { if (dict.count(s.substr(start, i)) && dp[start + i]) { vec.push_back(s.substr(start, i)); dfs140(s, dict, ans, vec, dp, start + i); vec.pop_back(); } } } vector<string> wordBreak(string s, unordered_set<string> &dict) { bool dp[s.size() + 1]; // 不同于上一题，这里需要多一位，最后一位为真，为了递归的时候方便 memset(dp, 0, sizeof(dp)); for (int i = 0; i < s.size(); i++) { if (dict.count(s.substr(i, s.size() - i))) dp[i] = 1; } for (int i = s.size() - 1; i < s.size(); i--) { if (dp[i] == false) { for (int j = i; j < s.size(); j++) { if (dict.count(s.substr(i, j - i + 1)) && dp[j + 1]) dp[i] = true; if (dp[i]) break; } } } dp[s.size()] = 1; vector<string> ans, tmp; dfs140(s, dict, ans, tmp, dp, 0); return ans; }};
这题的思路很像leetcode Palindrome Partitioning II
leetcode[140] Word Break II
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。