交错字符串

97. 交错字符串

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

示例 1:

1 2	输入: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac" 输出: true

示例 2:

1 2	输入: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc" 输出: false

首先我们需要理解「交错」这个概念，s3 由 s1 的部分字符和 s2 的部分字符交错形成，以示例 1 为例：

1 2	"aadbbcbcac" = "aa" + "db" + "bc" + "bca" + "c" s1 s2 s1 s2 s1

示例2中，s3 中剩下 “accc” ，s1 剩下 “cc” ，s2 剩下”ca”，”cc” 和 “ca” 无法交错形成 “accc”。

1 2	"aadbbbaccc" = "aa" + "dbb" + "b" + ... s1 s2 s1

可以将其当作不同路径来理解，下图来自gousiqi

首先，s1 和 s2 的长度之和不等于 s3 ，s3 必然不可能为 s1 和 s2 交错形成。我们定义 f(i, j)表示字符串 s1 的前 i 个字符能否与字符串 s2 的前 j 个字符形成字符串 s3 的前 i + j 个字符。如果 s1 的第 i 个字符与 s3 的第 i + j 个字符相等，那么 f(i, j)取决于 s1 的前 i - 1 个字符和 s2 的前 j 个字符能否交错构成 s3 的前 i + j - 1 个字符，表示为f(i - 1, j)。如果 s2 的第 j 个字符与 s3 的第 i + j 个字符相等，那么 f(i, j) 取决于 s1 的前 i 个字符和 s2 的前 j - 1 个字符能否交错构成 s3 的前 i + j - 1个字符，表示为f(i, j - 1)。我们可以得出动态规划方程：
$$
f(i,j)=[f(i - 1, j)\ and\ s_1[i]=s_3[i+j]]\ or\ [f(i, j - 1)\ and\ s_2[j] = s_3[i+j]]
$$
边界条件为 f(0, 0) = true。

class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
        int m = s1.length(), n = s2.length(), t = s3.length();
        if(m + n != t){
            return false;
        }

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

        for(int i = 0; i <= m; i++){
            for(int j = 0; j <= n; j++){
                int p = i + j - 1;
                if(i > 0){//注意字符串的下标与公式的区别
                    dp[i][j] = dp[i - 1][j] && s1.charAt(i - 1) == s3.charAt(p);
                }
				//两个条件之间是 “或” 的关系
                if(j > 0){
                    dp[i][j] = dp[i][j] || dp[i][j - 1] && s2.charAt(j - 1) == s3.charAt(p);
                }
            }
        }
        return dp[m][n];
    }
}

时间复杂度O(mn)，空间复杂度O(mn)。

我们还可以使用滚动数组来优化空间复杂度。

class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
        int m = s1.length(), n = s2.length(), t = s3.length();
        if(m + n != t){
            return false;
        }

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

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

                if(j > 0){
                    dp[j] = dp[j] || dp[j - 1] && s2.charAt(j - 1) == s3.charAt(p);
                }
            }
        }
        return dp[n];
    }
}

时间复杂度O(mn)，空间复杂度O(n)。