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”.
bool wordBreak(string s, unordered_set<string> &dict) { vector<bool>dp(s.size()+1,false); dp[0] = true; for(int i=0; i<s.size(); i++){ if(!dp[i]) continue; for(int j=i; j<s.size(); j++){ if(dict.find(s.substr(i,j-i+1)) != dict.end()){ dp[j+1] = true;//前j个字符可分 } if(dp[s.size()]) return true; } } return false;}
近期评论