LC

单词拆分
单词拆分II

思路

先考虑朴素做法，也就是枚举所有的子串，时间复杂度为$O(kn^3)$，$k$为词表大小，$n$为s的长度。

接下来考虑怎么优化，由于朴素枚举是每次遍历一个可能的方案。考虑能否每次遍历一类方案，也就是利用DP或者递推的思路。

集合表示： f[i]是一个布尔变量，它表示$S_1$-$S_i$是否能拆分成词表中的单词。

集合计算： f[i] = f[i - j] && S[j]-S[i]在词表中

时间复杂度$O(n^2)$，这里要做到$O(n^2)$必须保证查找字符串是否在词表中这一步的复杂度为$O(1)$，因此不能用库函数自带的哈希表（因为计算一个字符串的哈希值需要遍历一遍这个字符串，那么复杂度为$O(n)$），只能手写字符串哈希（因为在这个问题下可以优化）。

至于第二题，直接DFS找方案即可。

伪$O(n^2)$做法，实际上是$O(n^3)$

class Solution {
public:
    unordered_set<string> S;

    bool wordBreak(string s, vector<string>& wordDict) {
        for(auto &word : wordDict) S.insert(word);
        int n = s.size();
        vector<bool> f(n + 1);
        s = ' ' + s;

        f[0] = true;
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= i; j++) {
                if(S.count(s.substr(j, i - j + 1)) && f[j - 1])  // 每次需要计算substr的哈希值，是线性的时间复杂度
                    f[i] = true;
            }
        }

        return f[n];

    }   
};

手写哈希做法，真$O(n^2)$

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        typedef unsigned long long ULL;  // 相当于定义了模2^64下的加法运算，自带取模
        const int p = 131;  // p是经验值，一般取131，或者13331
        unordered_set<ULL> S;
        for(auto &word : wordDict) {
            ULL h = 0;
            for(auto c: word) h = h * p + c;
            S.insert(h);
        }

        int n = s.size();
        vector<bool> f(n + 1);
        s = ' ' + s;
        f[0] = true;

        for(int i = 0; i <= n; i++) {
            if(f[i]) {
                ULL h = 0;
                for(int j = i + 1; j <= n; j++) {  // 改变一下遍历顺序，方便计算哈希值
                    h = h * p + s[j];  // 注意这里是常数时间就得到了哈希值
                    if(S.count(h)) f[j] = true;
                }
            }
        }

        return f[n];
    }
};

单词拆分II

class Solution {
public:
    typedef unsigned long long ULL;
    const int P = 131;
    vector<string> ans;
    unordered_set<ULL> S;

    vector<string> wordBreak(string s, vector<string>& wordDict) {
        for(auto & word: wordDict){
            ULL h = 0;
            for(auto c: word) h = h * P + c;
            S.insert(h);
        }
        dfs(s, 0, "");
        return ans;    
    }

    void dfs(string& s, int u, string path) {
        if(u == s.size()) {
            path.pop_back();
            ans.push_back(path);
            return;
        }

        ULL h = 0;
        for(int i = u; i < s.size(); i++) {
            h = h * P + s[i];
            if(S.count(h)) { // 如果u-i这一段子串在词表中，则继续dfs
                dfs(s, i + 1, path + s.substr(u, i - u + 1) + " ");
            }
        }
    }
};