交错题库

交错字符串

给定三个字符串 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 + ...

示例1:

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

示例2:

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

示例3:

输入：s1 = "", s2 = "", s3 = ""
输出：true

方案动态规划

思路:

状态定义: dp[i][j]表示s1的前i个元素和s2的前j个元素是否能交错组成s3的前i+j个元素
状态转移方程:
- 如果i>0, 方程为:dp[i][j]=dp[i][j]||(dp[i-1][j]&&s1[i-1]==s3[p])
- 如果j>0, 方程为；dp[i][j]=dp[i][j]||(dp[i][j-1]&&s2[j-1]==s3[p])
初始化状态: dp[0][0]=true
问题答案: dp[n1][n2] 为最终答案

function isInterleave(s1, s2, s3) {
    const n1=s1.length;
    const n2=s2.length;
    const n3=s3.length;
    if(n1+n2!=n3){
        return false;
    }
    const dp=new Array(n1+1).fill(0).map(()=>new Array(n2+1).fill(false));
    dp[0][0]=true;
    for(let i=0;i<=n1;i++){
        for(let j=0;j<=n2;j++){
            let p=i+j-1;
            if(i>0){
                dp[i][j]=dp[i][j]||(dp[i-1][j]&&s1[i-1]==s3[p])
            }
            if(j>0){
                dp[i][j]=dp[i][j]||(dp[i][j-1]&&s2[j-1]==s3[p])
            }
        }
    }
    return dp[n1][n2];
};

数组第i行的状态只与第i-1行相关，我们可以用滚动数组优化空间复杂度

function isInterleave(s1, s2, s3) {
    const n1=s1.length;
    const n2=s2.length;
    const n3=s3.length;
    if(n1+n2!=n3){
        return false;
    }
    const dp=new Array(n2+1).fill(false);
    dp[0]=true;
    for(let i=0;i<=n1;i++){
        for(let j=0;j<=n2;j++){
            let p=i+j-1;
            if(i>0){
                dp[j]=dp[j]&&s1[i-1]==s3[p]
            }
            if(j>0){
                dp[j]=dp[j]||(dp[j-1]&&s2[j-1]==s3[p])
            }
        }
    }
    return dp[n2];
};

性能分析:

时间复杂度：O(nm)
空间复杂度：O(m)

交错字符串​

方案 动态规划​

交错字符串

方案动态规划