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".
首先说明：题意中，不要求是一一映射，只要s的子串在dict中有象就可以，不要求dict的原象都存在。比如：s = “aaaa"，dict = ["ab","aa"]，这也是满足的。
DP问题，但是解法和思路会有很多，这里给出三种不同的解法，虽说解法不同，但是整体的方向还是一致的，找到正确的状态方程就可以解决，这里可以用二维的状态变量，也可以用一维的，二维的用dp[ i， j]表示从i开始，长度为j的子串是否在字典里，那么即使这个整体不满足，我们还是要看能不能在这之间的部分找到k使得被k分割成的两部分都是满足的，则整体还是满足的，若不存在，则dp[i，j]就不满足了。最终的判断是看dp[0, |s| ] 。
这里的解法都用一维的状态。
第一种解法：
bool wordBreak(string s, unordered_set<string> &dict) {
vector<size_t> dp;
if(s.length() == 0 || dict.size() == 0) return false;
dp.push_back(0);//dp[0] = 0;
for (int len = 1; len <= s.size(); ++len)
{
for (int it = dp.size() - 1; it >= 0; --it)
{
string sub = s.substr(dp[it], len - dp[it]);
if(dict.find(sub) != dict.end())
{ dp.push_back(len); break; }
}
}
return dp[dp.size() - 1] == s.size();
}
这里我们用dp[ i ]来表示第i 个可以满足条件的长度，初始条件dp[0] = 0，最终我们判断最后的dp[ dp.size() - 1] == s.size().
第二种解法：
bool wordBreak(string s, unordered_set<string> &dict){
vector<bool> dp(s.length() + 1, false);
dp[0] = true;
for (int i = 0; i < s.size(); ++i)
{
if(dp[i] == false) continue;
unordered_set<string>::iterator it = dict.begin();
while (it != dict.end())
{
int len = (*it).size();
string sub = s.substr(i, len);
if((i + len) <= s.size() && dict.find(sub) != dict.end())
dp[i + len] = true;
++it;
}
}
return dp[s.length()];
}
这里我们总是在查看，从当前的i 点作为第一个元素，是否可以跟以后的元素匹配，使得构成的单词在dict中，若都不存在，那么这个点就不能作为起始点，我们在找下一个点的时候，要去找满足条件的点，因为不满足条件的点就没必要了，为什么？子问题不满足条件，整体肯定也不满足了。该算法实现的时间复杂度较低，是O（|S| * |dict|）
第三种解法，这个问题的解法其实跟我们开始论述的那个思路是一致的，只不过这里优化了空间复杂度。
class Solution {
public:
bool wordBreak(string s, unordered_set<string> &dict) {
vector<bool> dp(s.length() + 1, false);
dp[0] = true;
for (int i = 1; i <= s.length(); ++i)
for(int j = i - 1; j >= 0; --j)
{
if (dp[j] && dict.find(s.substr(j, i - j)) != dict.end())
{
dp[i] = true;
break;
}
}
return dp[s.length()];
}
};