拆分单词从递归到迭代

algorithm

---

拆分单词

• 拆分单词，题目大意，给定一个字符串$s$，和一个字典$wordDict$，问这个字符串能不能按照字典里的单词，拆分成字典里的单词组合。例如：
  $s = "leetcode", wordDict = ["leet", "code"]$，s可以拆分成$"leet","code"$两个单词。
• 理解这个题目之后，可以看出这个题目是类似于整数分割。在某个位置进行分割，假设为$i$,$s[0,i]$可以分割，$s[i+1,n-1]$也可以分割。那么整个字符串就是可以分割的。我们可以递归来解决这个问题。

方法一：递归

• 直观想法，求解的是$s[0,n-1]$是否可表示的结果，假设结果用$f[0,n-1]$表示，具体到基本的情况是什么样的呢？
• 基本情况是：一个字符串在词典中出现过。如果s的一个子串在字典中，那么这个就是基本的情况。假设$s[a,b]$表示的字符串在字典中，那么$f[a,b] = 1$。表示这个子串是可以用字典表示的。
• 同理：对于任意的$s[i,j]$子串，最后的结果有两种$f[i,j] = 1,f[i,j] = 0$。我们并不知道$f[i,j]$结果，但是其可以有更短的子串结果合成。也就是，$f[i,j]$能够表示为$s[i,k] + s[k+1,j]$，如果$s[i,k],s[k+1,j]$是可分割的子串，那么$s[i,j]$也是可以分割的子串。那么我们就递归的求解$f[i,k],f[k+1,j]$

$$f[i,j] = max_{k=i}^{j-1}(f[i,k] \&\& f[k+1,j])$$

• 讨论递归出口
• 1.1 i>j || j >= s.size()
• s[i,j] 是字典里的单词。

    unordered_map<string, int> umap;
    bool wordbreak(string s, vector<string>& wordDict)
    {
        int n = s.size();
        for (auto& e : wordDict)
            umap[e] = 1;
        return wordBreak2(s, 0, n - 1);
    }
    bool wordBreak2(string s, int i, int j)
    {
        int n = s.size();
        if (i > j || j >= n) // base case #1
            return 0;
        string str = string(s.begin() + i, s.begin() + j + 1);
        if (umap.find(str) != umap.end()) { // base case #2
            return 1;
        }
        for (int k = i; k < j; ++k) {
            int x = wordBreak2(s, i, k);
            if (!x)// prune for false substr s[i,k]
                continue;
            int y = wordBreak2(s, k + 1, j);
            if (x && y)
                return 1;
        }
        return 0;
    }

• 时间复杂度:$T(n) =O(2^n)$。
• 空间复杂度:函数调用

方法二：转化为备忘录递归

• 上述方式存在子问题重复计算的情况，例如计算$f[0,n-1]$,需要计算 $f[0,k] \cdots f[k+1,n-1]$,$f[1,n-1]$需要计算，$f[1,k],f[k+1,n-1]...$，,可以发现非常多的子问题需要重新计算，我们用map，也可以用数组，来缓存已经计算完的数据。对于已经获取的数据直接返回结果。
• 对于已经计算出来的符号排列结果用map来保存，例如map[0-10]=1，表示$s[0,10]$的子串，是否可分割。

    unordered_map<string, int> umap;
    unordered_map<string, int> rmap;
    bool wordbreak3(string s, vector<string>& wordDict)
    {
        int n = s.size();
        for (auto& e : wordDict)
            umap[e] = 1;
        return wordBreak2(s, 0, n - 1);
    }
    bool wordBreak3(string s, int i, int j)
    {
        int n = s.size();
        if (i > j || j >= n)
            return 0;
        string key = to_string(i) + "-" + to_string(j);
        if (rmap.find(key) != rmap.end()) {// has cached result s[i,j]
            return rmap[key];
        }
        string str = string(s.begin() + i, s.begin() + j + 1);
        if (umap.find(str) != umap.end()) { // base case for w in dictionary
            rmap[key] = 1;
            return 1;
        }
        for (int k = i; k < j; ++k) {
            int x = wordBreak2(s, i, k);
            if (!x)// prone the result s[i,k]
                continue;
            int y = wordBreak2(s, k + 1, j);
            if (x && y) {
                rmap[key] = 1; //cache result s[i,j]
                return 1;
            }
        }
        rmap[key] = 0;// cache result s[i,j]
        return 0;
    }

• 时间复杂度：$T(n) = O(n^2)$，子问题个数为$O(n^2)$。
• 空间复杂度：$O(n^2)$，需要使用哈希表，存储子问题的结果。

方法三：拆分单词（转化为迭代计算）

• 从第二步，能看出，我们可以从基本情况（小规模的问题），来推导更为大的规模。
• 假设$f[i,j]$ 表示$s[i,j]$能否被拆分。

$$f[i,j] = max_{k=i}^{j-1}(f[i,k] \&\& f[k+1,j])$$

• 我们可以按照子串的长度来扩展。由$l=0,l=1,l=2 \cdots l=n$
• 基础情况：$f[i,j] = {s[i,j] \in wordDict}$

bool wordBreak(string s, vector<string>& wordDict)
    {
        for (auto& e : wordDict)
            umap[e] = 1;
        int n = s.size();
        int f = 0;
        vector<vector<int>> dp(n, vector<int>(n, 0));
        for (int l = 0; l <= n; l++) {
            for (int i = 0; i < n - l; i++) {
                int j = i + l;
                if (j >= n)
                    break;
                string str(s.begin() + i, s.begin() + j + 1);
                if (umap.find(str) != umap.end()) {
                    dp[i][j] = 1;
                    f = 1;
                }
            }
        }
        if (f == 0) {
            return 0;
        }
        if(dp[0][n-1])
            return 1;
        for (int l = 0; l < n; l++) {
            for (int i = 0; i < n - l; ++i) {
                int j = i + l;
                if (dp[i][j] == 1)
                    continue;
                for (int k = i; k < j; ++k) {
                    int c = dp[i][k] && dp[k + 1][j];
                    dp[i][j] = max(c, dp[i][j]);
                    if (dp[i][j])
                        break;
                }
            }
        }
        return dp[0][n - 1];
    }

• 时间复杂度:$O(n^3)$,空间复杂度：$O(n^2)$
• 这里的空间方面可以优化，比如初始化的时候，可以按照字典单词最小长度的单词初始化