LC 139. Word Break

https://leetcode.com/problems/word-break/description/?envType=study-plan-v2&envId=top-interview-150

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        int n = s.size();
        unordered_set<string> dict;
        for (auto &x: wordDict) dict.insert(x);
        vector<bool> f(n, false);
        for (int i = 0; i < n; i++) {
            string cur = "";
            for (int j = i; j >= 0; j--) {
                cur = s[j] + cur;
                if (j == 0 || (j - 1 >= 0 && f[j - 1])) {
                    if (dict.count(cur)) {
                        f[i] = true;
                        break;
                    }
                }
                if (f[i]) break;
            }
        }
        return f[n - 1];
    }
};

當我們在決定以 index = i 作為結尾是否合法的時候，他可能是從前面的 j 往後轉移的，也就是如果 index = j 作為結尾是合法的時候，只要 s[j + 1, i] 是有在 wordDict 當中，那麼就可以說明以 index = i 作為結尾是合法的。