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".
[解题思路]
DP: ans[i]表示s的下标0~i子串是否可以被dict表示
ans[i] = 存在k满足ans[k]&dict.contains(s.substr(k+1, i-k))==true即可.
1 bool Solution::wordBreak(std::string s, std::tr1::unordered_set<std::string> &dict) 2 { 3 if (s.length() == 0 || dict.size()==0) 4 { 5 return false; 6 } 7 int length = s.length(); 8 bool ans[length]; 9 for (int i = 0; i < length; i++) 10 ans[i] = false; 11 for (int i = 0; i < length; i++) 12 { 13 if (dict.find(s.substr(0, i+1)) != dict.end()) 14 ans[i] = true; 15 for (int j = 0; j < i; j++) 16 { 17 if (ans[j]&&dict.find(s.substr(j+1, i-j))!=dict.end()) 18 { 19 ans[i] = true; 20 break; 21 } 22 } 23 } 24 return ans[length-1]; 25 }
leetcode -- word break,布布扣,bubuko.com
原文：http://www.cnblogs.com/taizy/p/3904979.html