分析

• 本题的考点：动态规划。

• 分析如下：

代码

• C++

class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {

        int n = s1.size(), m = s2.size();
        if (s3.size() != n + m) return false;

        vector<vector<bool>> f(n + 1, vector<bool>(m + 1));
        s1 = ' ' + s1, s2 = ' ' + s2, s3 = ' ' + s3;
        for (int i = 0; i <= n; i++)
            for (int j = 0; j <= m; j++) {
                if (!i && !j) f[i][j] = true;
                else {
                    if (i && s1[i] == s3[i + j]) f[i][j] = f[i - 1][j];
                    if (j && s2[j] == s3[i + j]) f[i][j] = f[i][j] || f[i][j - 1];
                }
            }
        return f[n][m];
    }
};

• Java

class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {

        int n = s1.length(), m = s2.length();
        if (s3.length() != n + m) return false;

        char[] cs1 = (" " + s1).toCharArray();
        char[] cs2 = (" " + s2).toCharArray();
        char[] cs3 = (" " + s3).toCharArray();

        boolean[][] f = new boolean[n + 1][m + 1];
        for (int i = 0; i <= n; i++)
            for (int j = 0; j <= m; j++) 
                if (i == 0 && j == 0) f[i][j] = true;
                else {
                    if (i != 0 && cs1[i] == cs3[i + j]) f[i][j] = f[i - 1][j];
                    if (j != 0 && cs2[j] == cs3[i + j]) f[i][j] = f[i][j] || f[i][j - 1];
                }
        return f[n][m];
    }
}

时空复杂度分析

• 时间复杂度：$O(n \times m)$，n、m分别为s1、s2长度。

• 空间复杂度：$O(n \times m)$。