交错字符串

题目描述

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

解题思路

深度优先遍历

借助于辅助函数 isInterleave(String s1, String s2, String s3, int st1, int st2, int st3)，判断 s1[st1:] 与 s2[st2:] 是否能形成 s3[st3:] 所示的交错字符串，因此原问题变为了 isInterleave(s1, s2, s3, 0, 0, 0)。

对于 isInterleave(s1, s2, s3, st1, st2, st3) 的求解则可以递归调用自己，如果 s1[st1] == s2[st2] == s3[st3]，说明 s1[st1] 和 s2[st2] 都可作为 s3[st3]，此时便衍生为两种可能， s1[st1] 作为 s3[st3] 产生的结果为 isInterleave(s1, s2, s3, st1 + 1, st2, st3 + 1)，或者 s2[st2] 作为 s3[st3] 产生的结果为 isInterleave(s1, s2, s3, st1, st2 + 1, st3 + 1)，无论这两种可能哪一种为真，那么最终的结果就是真，如果都为假，就说明无法形成指定的交错字符串。

如果只有 s1[st1] == s3[st3]，则递归调用 isInterleave(s1, s2, s3, st1 + 1, st3 + 1)，如果只有 s2[st2] == s3[st3]，则递归调用 isInterleave(s1, s2, s3, st1, st2 + 1, st3 + 1)，否则 s1 与 s2 的首字符都与 s3 的首字符不同，则无论怎样都无法形成 s3 所示的交错字符，返回结果为 false。

public boolean isInterleave(String s1, String s2, String s3) {
    if (s1.length() + s2.length() != s3.length()) {
        return false;
    }
    return isInterleave(s1, s2, s3, 0, 0, 0);
}
private boolean isInterleave(String s1, String s2, String s3, int st1, int st2, int st3) {
    if (st1 == s1.length()) {
        return s2.substring(st2).equals(s3.substring(st3));
    }

    if (st2 == s2.length()) {
        return s1.substring(st1).equals(s3.substring(st3));
    }

    char c1 = s1.charAt(st1);
    char c2 = s2.charAt(st2);
    char c3 = s3.charAt(st3);

    if (c1 != c3 && c2 != c3) {
        return false;
    } else if (c1 == c3 && c2 == c3) {
        return isInterleave(s1, s2, s3, st1 + 1, st2, st3 +1) || isInterleave(s1, s2, s3, st1, st2 + 1, st3 +1);
    } else if (c1 == c3) {
        return isInterleave(s1, s2, s3, st1 + 1, st2, st3 +1);
    } else {
        return isInterleave(s1, s2, s3, st1, st2 + 1, st3 +1);
    }
}

此方法运行超时，未能通过最后一个测试用例。

动态规划

我们定义一个函数 dp[i, j] 表示 s1 的前 i 个字符与 s2 的前 j 个字符能否形成 s3 前 i + j 个字符所示交错字符串，定义 l1 为 s1 的长度，l2 为 s2 的长度，则原问题结果为求解 dp[l1][l2] 的值。

而 dp[i][j] 的取值可如下确定

如果 s1[i - 1] == s3[i + j - 1] 并且 dp[i - 1][j] 为 true，则 dp[i][j] 为 true
如果 s2[j - 1] == s3[i + j - 1] 并且 dp[i][j - 1] 为 true，则 dp[i][j] 为 true
否则 dp[i][j] 为 false

注：编程中字符的索引从 0 开始，所以 i - 1 表示第 i 个字符，另 s1 等不是数组，为了讲解方便使用 [i] 的形式进行索引，实际编程应使用特定的 API 访问，如 charAt(i)。

所以 dp[i][j] 的递归公式为

dp[i][j] = (s1[i - 1] == s3[i + j - 1] && dp[i - 1][j]) || (s2[j - 1] == s3[i + j - 1] && dp[i][j - 1])

具体编程时还应考虑 (i - 1) 与 (j - 1) 是否越界，所以上面的程序可以修改为

if (i > 0) {
    dp[i][j] = dp[i][j] || (dp[i - 1][j] && s1.[i - 1] == s3[i + j - 1]);
}
if (j > 0) {
    dp[i][j] = dp[i][j] || (dp[i][j - 1] && s2.[j - 1] == s3.[i + j - 1]);
}

完整程序如下

public boolean isInterleave(String s1, String s2, String s3) {
    int l1 = s1.length();
    int l2 = s2.length();
    int l3 = s3.length();
    if (l1 + l2 != l3) {
        return false;
    }
    boolean[][] dp = new boolean[l1 + 1][l2 + 1];
    dp[0][0] = true;
    for (int i = 0; i <= l1; i++) {
        for (int j = 0; j <= l2; j++) {
            if (i > 0) {
                dp[i][j] = dp[i - 1][j] && s1.charAt(i - 1) == s3.charAt(i + j - 1);
            }
            if (j > 0) {
                dp[i][j] = dp[i][j] || (dp[i][j - 1] && s2.charAt(j - 1) == s3.charAt(i + j - 1));
            }
        }
    }
    return dp[l1][l2];
}

优化：空间压缩

考虑到 dp[i][j] 每次只用了 dp[i - 1] 这上一层的数据，因此我们没有必要使用一个二维数组保存状态，使用一个一维数组即可，修改上面的程序如下

public boolean isInterleave(String s1, String s2, String s3) {
    int l1 = s1.length();
    int l2 = s2.length();
    int l3 = s3.length();
    if (l1 + l2 != l3) {
        return false;
    }
    boolean[] dp = new boolean[l2 + 1];
    dp[0] = true;
    for (int i = 0; i <= l1; i++) {
        for (int j = 0; j <= l2; j++) {
            if (i > 0) {
                dp[j] = dp[j] && s1.charAt(i - 1) == s3.charAt(i + j - 1);
            }
            if (j > 0) {
                dp[j] = dp[j] || (dp[j - 1] && s2.charAt(j - 1) == s3.charAt(i + j - 1));
            }
        }
    }
    return dp[l2];
}