LeetCode HOT100 - 单词拆分

1 <= s.length <= 300 可以用比较暴力的思路

比如枚举每一个转移点

也就是说我们令 dp[i] 表示到 i 为止能不能组合出来

每次转移就是从前面所有的位置转移过来，判断这个字串是否在字典中

vector 如果要查找的话只能使用 count(a.begin(), a.end(), x) 之类的形式，没有内置的 count 或者 find 函数

可以换成 unordered_set 之类的形式来做

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

当然，可以加一些剪枝，比如逆序找转移点，距离大于字典中单词的最大长度就跳过之类

不过直接这样写也能过