一个没有把百酒都尝遍的人，是不会体会到清水之味的~

[问题描述]

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
     
       &dict) 2 { 3     if (s.length() == 0 || dict.size()==0) 4         return false; 5     int length = s.length(); 6     bool ans[length]; 7     for (int i = 0; i < length; i++) 8         ans[i] = false; 9     for (int i = 0; i < length; i++){10         if (dict.find(s.substr(0, i+1)) != dict.end())11             ans[i] = true;12         for (int j = 0; j < i; j++)13             if (ans[j]&&dict.find(s.substr(j+1, i-j))!=dict.end()){14                 ans[i] = true;15                 break;16             }17     }18     return ans[length-1];19 }