题解 | #交错编号#

知识点：

动态规划

分析：

首先如果 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 s1, string s2, string s3) {
        int len1 = s1.size(), len2 = s2.size(), len3 = s3.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 && s3[i + j - 1] == s1[i - 1])
                    f[i][j] |= f[i - 1][j];
                if(j > 0 && s3[i + j - 1] == s2[j - 1])
                    f[i][j] |= f[i][j - 1];
            }
        return f[len1][len2];
    }