题解 | #交织子序列#

知识点：

动态规划

分析：

首先如果 s3 的长度不等于 s1 的长度 + s2 的长度，肯定返回 false

如果两个指针分别指向 s1 和 s2，然后遍历 s3，如果 s3 对应的字符出现在 s1，指向 s1 的指针前进一位，反之指向 s1 的指针前进一位。

用 f[i][j] 来表示 s1 的前 i 位和 s2 的前 j 位是否可以组成 s3 的前 i + j 位，那么

如果 s3[i + j - 1] == s1[i - 1]，f[i][j] |= f[i - 1][j]

如果 s3[i + j - 1] == s2[j - 1]，f[i][j] |= f[i][j - 1]

如果 s3[i + j - 1] == s1[i - 1] && s3[i + j - 1] == s2[j - 1]，f[i][j] = f[i - 1][j] || f[i][j - 1] || f[i][j]

否则 f[i][j] = false

编程语言：

C++

完整代码：

    bool isInterleave(string s, string x, string t) {
        int len1 = s.size(), len2 = x.size(), len3 = t.size();
        if(len1 + len2 != len3) return false;
        vector<vector<int>> f(len1 + 1, vector<int>(len2 + 1, false));
        f[0][0] = true;
        for(int i = 0; i <= len1; i ++)
            for(int j = 0; j <= len2; j ++){
                if(i > 0 && t[i + j - 1] == s[i - 1])
                    f[i][j] |= f[i - 1][j];
                if(j > 0 && t[i + j - 1] == x[j - 1])
                    f[i][j] |= f[i][j - 1];
            }
        return f[len1][len2];
    }

备注：此题与同站NB129题目相同。

滚动数组优化代码：

	bool isInterleave(string s, string x, string t) {
        auto f = vector <int> (x.size() + 1, false);
        int n = s.size(), m = x.size(), k = t.size();
        if (n + m != k) return false;
        f[0] = true;
        for (int i = 0; i <= n; ++i) {
            for (int j = 0; j <= m; ++j) {
                int p = i + j - 1;
                if (i > 0) {
                    f[j] &= (s[i - 1] == t[p]);
                }
                if (j > 0) {
                    f[j] |= (f[j - 1] && x[j - 1] == t[p]);
                }
            }
        }
        return f[m];
    }