算法

(DP) $O(n^2)$

二维dp。我们约定 dp[i][j]代表s1的前i个字母和s2的前j个字母是否能构成 s3的 当前第i+j个字母。若能构成，dp值为1，若不能dp值为0。

然后，我们考虑状态转移方程。为了便于叙述，这里的转移我们从前往后考虑。即如何从 dp[i][j]往后进行转移。

我们可以发现，如果当前的dp值为0,也就是s1的前i个和s2的前j个已经无法构成s3的前i+j个了，那么根本无需再考虑后续情况。

若当前的dp值为1，也就是s1的前i个和s2的前j个可以构成s3的前i+j个（无需考虑是怎么构成的）。那么我们看此时，能否将s1的第i+1个或s2的第j+1个贴到已经形成的字符串的末尾，去构成s3的前i+j+1个。如果可以，那么我们进行状态转移，不行就放弃。

• 初始化dp值。
• 二维dp,依照刚才的动态转移方程，看是否能往后转移。或者看能否有前继状态转移到当前态，能则转移。
• 最后输出 dp[|s1|][|s2|] 即可。

C++ 代码

class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
        if (s1.length() + s2.length() != s3.length()) {
            return false;
        }

        bool interleave[s1.length() + 1][s2.length() + 1];
        interleave[0][0] = true;
        for (int i = 1; i <= s1.length(); i++) {
            interleave[i][0] = interleave[i - 1][0] && s1[i - 1] == s3[i - 1];
        }
        for (int i = 1; i <= s2.length(); i++) {
            interleave[0][i] = interleave[0][i - 1] && s2[i - 1] == s3[i - 1];
        }

        for (int i = 1; i <= s1.length(); i++) {
            for (int j = 1; j <= s2.length(); j++) {
                interleave[i][j] = false;
                if (s1[i - 1] == s3[i + j - 1]) {
                    interleave[i][j] = interleave[i][j] || interleave[i - 1][j];
                }
                if (s2[j - 1] == s3[i + j - 1]) {
                    interleave[i][j] = interleave[i][j] || interleave[i][j - 1];
                }
            }
        }

        return interleave[s1.length()][s2.length()];
    }
};

Java 代码

class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
        // s1: [0 ... i ... n-1]
        // s2: [0 ... i ... m-1]
        // s3: [0 ... i+j ... n+m-1]
        // dp[i][j]: s1[i->n-1] + s2[j->m-1] => s3[i+j->n+m-1]
        // 1. s1[i] = s2[j]
        // 1) s1[i] = s3[i+j]
        // dp[i][j] = dp[[i+1][j] || dp[i][j+1]
        // 2) s1[i] != s3[i+j]
        // dp[i][j] = false
        // 2. s1[i] != s2[j]
        // 1) s1[i] = s3[i+j]
        // dp[i][j] = dp[i+1][j]
        // 2) s2[j] = s3[i+j]
        // dp[i][j] = dp[i][j+1]
        // 3) s1[i] != s2[j] != s3[i+j]
        // dp[i][j] = false
        // dp[n][m] = true
        // dp[n][j] = s2[j->.] == s3[i+j->.]  0 <= j <= m-1
        // dp[i][m] = s1[i->.] == s3[i+j->.]  0 <= j <= n-1
        int n = s1.length();
        int m = s2.length();
        if (n + m != s3.length()) return false;
        boolean[] prev = new boolean[m + 1];
        for (int i = n; i >= 0; --i) {
            boolean[] dp = new boolean[m + 1];
            for (int j = m; j >= 0; --j) {
                if (i == n && j == m) dp[j] = true;
                else if (i == n) dp[j] = s2.substring(j).equals(s3.substring(i+j));
                else if (j == m) dp[j] = s1.substring(i).equals(s3.substring(i+j));
                else {
                    char a = s1.charAt(i);
                    char b = s2.charAt(j);
                    char c = s3.charAt(i + j);
                    if (a == b) {
                        if (a == c) dp[j] = prev[j] || dp[j + 1];
                    }
                    else {
                        if (a == c) dp[j] = prev[j];
                        else if (b == c) dp[j] = dp[j + 1];
                    }
                }
            }
            prev = dp;
        }
        return prev[0];
    }
}