题目描述

给定三个字符串 s1, s2, s3, 验证 s3 是否是由 s1 和 s2 交错组成的。

样例1

输入：s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
输出：true

样例2

输入：s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
输出：false

算法1

(动态规划) $O(n^2)$

* 状态表示：f[i][j]表示s3(0,i+j)能否由s1(0,i)和s2(0,j)交错组成， 属性：boolean
* 状态计算：f[i][j]划分为两个子集
    1.s3(i+j)属于s1，需要s3(i+j) == s1(i) 且 f[i][j] = f[i-1][j]
    2.s3(i+j)属于s2，需要s3(i+j) == s1(i) 且 f[i][j] = f[i][j-1]

Java 代码

class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
        int n = s1.length(), m = s2.length();
        if(s3.length() != m+n) return false;
        s1 = " " + s1;
        s2 = " " + s2;
        s3 = " " + s3;
        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 && s1.charAt(i) == s3.charAt(i+j)) f[i][j] = f[i-1][j];
                    if(j != 0 && s2.charAt(j) == s3.charAt(i+j)) f[i][j] = f[i][j] || f[i][j-1];
                }
            }
        }

        return f[n][m];
    }
}