题解 | #交错编号# Java

可以使用动态规划的方法进行求解。

定义一个二维数组dp，其中dp[i][j]表示字符串s1的前i个字符和字符串s2的前j个字符是否可以交错组成字符串s3的前i+j个字符。

首先，我们需要初始化dp数组的边界条件。当s1和s2都为空串时，也就是i=0且j=0时，dp[0][0]为true。当s1为空串时，也就是i=0且j≥1时，dp[0][j]等于s2的前j个字符是否与s3的前j个字符相等。同理，当s2为空串时，也就是i≥1且j=0时，dp[i][0]等于s1的前i个字符是否与s3的前i个字符相等。

然后，我们可以通过递推关系式来更新dp数组的其他位置。对于dp[i][j]，如果s1的第i个字符等于s3的第i+j个字符，说明s1的第i个字符可以和s3的第i+j个字符匹配，此时可以继续判断s1的前i-1个字符和s2的前j个字符是否可以交错组成s3的前i+j-1个字符，即dp[i][j] = dp[i-1][j]。同理，如果s2的第j个字符等于s3的第i+j个字符，说明s2的第j个字符可以和s3的第i+j个字符匹配，此时可以继续判断s1的前i个字符和s2的前j-1个字符是否可以交错组成s3的前i+j-1个字符，即dp[i][j] = dp[i][j-1]。

最后，遍历完整个dp数组后，判断dp[s1.length()][s2.length()]的值即可，如果为true，则说明s3可以由s1和s2交错组成，否则不可以。

import java.util.*;


public class Solution {

    public boolean isInterleave(String s1, String s2, String s3) {
        int m = s1.length();
        int n = s2.length();
        int k = s3.length();

        if (m + n != k) {
            return false;
        }

        boolean[][] dp = new boolean[m + 1][n + 1];
        dp[0][0] = true;

        for (int i = 1; i <= m; i++) {
            if (s1.charAt(i - 1) != s3.charAt(i - 1)) {
                break;
            }
            dp[i][0] = true;
        }

        for (int j = 1; j <= n; j++) {
            if (s2.charAt(j - 1) != s3.charAt(j - 1)) {
                break;
            }
            dp[0][j] = true;
        }

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if ((s1.charAt(i - 1) == s3.charAt(i + j - 1) && dp[i - 1][j])
                        || (s2.charAt(j - 1) == s3.charAt(i + j - 1) && dp[i][j - 1])) {
                    dp[i][j] = true;
                }
            }
        }

        return dp[m][n];
    }
}