首页 > 代码库 > Word Break II
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.
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) { int len = s.length(); for(int i=0; i<len; i++){ vector<int> tmp(len, 0); dp.push_back(tmp); } vector<bool> reach(len, false); for(int i=0; i<len; i++){ if(i>0 && !reach[i-1]) continue; for(int j=i; j<len; j++){ string sub = s.substr(i, j-i+1); if(dict.find(sub) != dict.end()) { reach[j] = true; dp[i][j] = 1; } } } string str = ""; if(reach[len-1]) helper(0, len, str, s); return ans; } void helper(int ind, int len, string str, string s){ if(ind == len) { ans.push_back(str.substr(0, str.length()-1)); return; } for(int i=ind; i<len; i++){ if(dp[ind][i] == 1){ string nstr = str + s.substr(ind, i-ind+1) + " "; helper(i+1, len, nstr, s); } } } vector<vector<int> > dp; vector<string> ans;};
Word Break II
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。