leetcode - 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".

class Solution {
public:
    bool wordBreak(std::string s, std::unordered_set<std::string> &dict) {
        int n = (int)s.size();
		std::vector<int> dp(n+1,0);
		dp[0] = 1;
		for(int i = 1; i <= n; i++)
		{
			if(dp[i-1])
			{
				int index = i - 1;
				for(int j = index; j < n; j++)
				{
					std::string str = s.substr(index,j-index+1);
					if(dict.count(str) > 0)
						dp[j+1] = true;
				}
			}
		}
		return dp[n];
    }
};

leetcode - Word Break

原文：http://blog.csdn.net/akibatakuya/article/details/39459587