Word Break

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();
	}

第二种解法：

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()];
	}

第三种解法，这个问题的解法其实跟我们开始论述的那个思路是一致的，只不过这里优化了空间复杂度。

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()];
	}
};

Word Break

原文：http://blog.csdn.net/shiquxinkong/article/details/18230523