题解 | #训练聪明的牛# 反向构造哈希表 + 动态规划

知识点

哈希表动态规划

思路

定义状态表示f[i] 表示前i个字母能否被合法分割; 那么只需要枚举当前字母所在的子串, 查询是否在wordList即可进行转移。

使用哈希表将所有的word存起来可以做到O(len)的时间内查询是否存在；在枚举子串的时候倒着枚举可以减少复制字符串的时间消耗.

时间复杂度 $O(nm^2)$ 字符串长度为m

AC Code (C++)

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @param wordDict string字符串vector 
     * @return bool布尔型
     */
    bool wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string> S;
        for (auto& ss : wordDict) {
            reverse(ss.begin(), ss.end());
            S.insert(ss);
        }

        int n = s.size();
        vector<bool> f(n + 1, false);
        f[0] = true;
        for (int i = 1; i <= n; i ++) {
            string cur;
            for (int j = i - 1; j >= 0; j --) {
                cur += s[j];
                if (S.count(cur)) f[i] = (f[i] or f[j]);
                if (f[i] or cur.size() > 25) break;
            }
        }
        return f[n];
    }
};