[LeetCode]Word Break

很直观的递归题目，但是backtracking会超时，我们要用DP来优化。DP[i]表示string的前i个字符能否成功break，我们有递推公式：

• DP[i] = true, if我们有 j, where s[j, i]在字典里，并且DP[i] == true
• 否则，DP[i] = false

时间复杂度O(n^2)，空间复杂度O(n)，代码如下:

	class Solution {
	public:
	bool wordBreak(string s, vector<string>& wordDict) {
	int len = s.size();
	unordered_set<string> dict(wordDict.begin(), wordDict.end());
	vector<bool> dp(len + 1, false);
	dp[0] = true;
	for(int i = 0; i < len; ++i)
	{
	for(int j = 0; j <= i; ++j)
	{
	string str = s.substr(j, i - j + 1);
	if(dict.find(str) != dict.end() && dp[j])
	{
	dp[i + 1] = true;
	break;
	}
	}
	}
	return dp[len];
	}
	};

view raw Word Break.cpp hosted with ❤ by GitHub