本文共 2157 字，大约阅读时间需要 7 分钟。

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
   
     &dict) {		vector
    
      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
   
     &dict){		vector
    
      dp(s.length() + 1, false);		dp[0] = true;		for (int i = 0; i < s.size(); ++i)		{			if(dp[i] == false) continue;			unordered_set
     
      ::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
   
     &dict) {		vector
    
      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()];	}};
    
   

转载地址：http://wrlji.baihongyu.com/