题目链接：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”.

这道题的要求是判断一个字符串能否由字典dict中的单词拼接而成。

直接上动态规划，先考虑怎么存储每一步的结果。可以采用dp[i]表示前i个字符能否由字典dict中的单词拼接而成，那么初始值为false，除了dp[0]为true。

接下来，考虑递推公式。遍历到第i+1个字符的时候，可以将前面i+1个字符分成2部分，前一部分可以在dp数组中直接查到，后一部分去dict中查找，如果两部分结果都为true，那么dp[i]为true。因此递推公式为：

    for(int j = 0; j <= i; ++ j)
        if(dp[j] && dict.find(s.substr(j, i - j + 1)) != dict.end())
        {
            dp[i + 1] = true;
            break;
        }

其中，j是用于将前面i+1个字符分割成两部分的。

时间复杂度：O(n2)

空间复杂度：O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

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