leetcode[139] Word Break

给一个字符串，判断是否能够分为若干个部分，并且每个部分都能在字典dict里面找到。有的话就返回true。例如：

For example, given
s = "leetcode",
dict = ["leet", "code"].

Return true because "leetcode" can be segmented as "leet code".

思路：利用动态规划，一开始初始化的时候数组dp[]存的是每个位置到终点的词是否在词典里。如果是存true。

然后从后往前，判断当前的dp[i]是否为true，是的话就直接--，如果不是就判断有没有可能变为true，判断能不能变为true就是遍历从i到结尾的每个字词是否存在dict中并且字词之后的部分dp[]为true。

随后就是看dp[0]是false还是true了

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

这题好像个之前做过的leetcode Palindrome Partitioning II有相似的地方。这题比它容易一些。