Leetcode No.97 交错字符串

一、题目描述

给定三个字符串 s1、s2、s3，请你帮忙验证 s3 是否是由 s1 和 s2 交错 组成的。

两个字符串 s 和 t 交错 的定义与过程如下，其中每个字符串都会被分割成若干 非空 子字符串：

s = s1 + s2 + ... + sn t = t1 + t2 + ... + tm |n - m| <= 1 交错 是 s1 + t1 + s2 + t2 + s3 + t3 + ... 或者 t1 + s1 + t2 + s2 + t3 + s3 + ... 提示：a + b 意味着字符串 a 和 b 连接。

示例 1：

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

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

示例 3： 输入：s1 = "", s2 = "", s3 = "" 输出：true

提示：

0 <= s1.length, s2.length <= 100 0 <= s3.length <= 200 s1、s2、和 s3 都由小写英文字母组成

二、解题思路

首先如果 |s1| + |s2| != |s3|,那 s3必然不可能由 s1和 s2交错组成。 在 |s1| + |s2| = |s3|时，我们可以用动态规划来求解。 我们定义 f(i, j)表示 s1的前 i 个元素和 s2的前 j 个元素是否能交错组成 s3的前 i+j 个元素。 如果 s1的第 i 个元素和 s3的第 i + j 个元素相等，那么 s1的前 i 个元素和 s2的前 j 个元素是否能交错组成s3的前 i + j个元素取决于 s1的前 i - 1个元素和 s2的前 j 个元素是否能交错组成 s3的前 i + j - 1个元素， 即此时 f(i, j) 取决于 f(i - 1, j)，在此情况下如果 f(i - 1, j) 为真，则 f(i, j) 也为真。 同样的，如果 s2的第j 个元素和 s3的第 i + j个元素相等并且 f(i, j - 1)为真，则 f(i, j) 也为真。 于是我们可以推导出这样的动态规划转移方程： f(i,j)=[f(i−1,j) && s1(i−1)=s3(p)] || [f(i,j−1) && s2(j−1)=s3(p)] 其中 p = i + j - 1。边界条件为f(0,0)=True。

三、代码

public class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
        int n1=s1.length();
        int n2=s2.length();
        int n3=s3.length();
        if(n1+n2!=n3){
            return false;
        }
        boolean[][] bool=new boolean[n1+1][n2+1];
        bool[0][0]=true;
        for(int i=0;i<=n1;i++){
            for(int j=0;j<=n2;j++){
                int p=i+j-1;
                if(i>0){
                    bool[i][j]=bool[i][j]||bool[i-1][j]&&s1.charAt(i-1)==s3.charAt(p);
                }
                if(j>0){
                    bool[i][j]=bool[i][j]||bool[i][j-1]&&s2.charAt(j-1)==s3.charAt(p);
                }
            }
        }
        return bool[n1][n2];
    }

    public static void main(String[] args) {
        Solution solution=new Solution();
        String s1="aabcc";
        String s2="dbbca";
        String s3="aadbbcbcac";
        System.out.println(solution.isInterleave(s1,s2,s3));
    }
}

四、复杂度分析

时间复杂度和空间复杂度都是 O(nm)，其中n是字符串s1的长度，m是字符串s2的长度。