题目描述

交错字符串：给定三个字符串 s1、s2 和 s3，判断 s3 是否可以由 s1 和 s2 交错组成。即，s3 中的字符是否恰好可以由 s1 和 s2 中的字符按照某种顺序依次取出组成，且 s1 和 s2 中的每个字符至多被使用一次。

示例：

• 输入：s1 = "aab", s2 = "xyb", s3 = "aaxyb"
• 输出：true
• 解释：s3 可以由 s1 和 s2 交错组成，如 "aaxyb" 可以通过 "aa"（来自 s1）和 "xyb"（来自 s2）交错组成。

PHP 示例代码

function isInterleave(string $s1, string $s2, string $s3) {
    $len1 = strlen($s1);
    $len2 = strlen($s2);
    $len3 = strlen($s3);

    // 如果 s1 和 s2 的长度之和不等于 s3 的长度，则无法交错组成
    if ($len1 + $len2 !== $len3) {
        return false;
    }

    // 创建一个二维数组来保存中间结果
    $dp = array_fill(0, $len1 + 1, array_fill(0, $len2 + 1, false));
    $dp[0][0] = true; // 空字符串可以由空字符串交错组成

    // 初始化第一行和第一列
    for ($i = 1; $i <= $len1; $i++) {
        $dp[$i][0] = $dp[$i - 1][0] && $s1[$i - 1] === $s3[$i - 1];
    }
    for ($j = 1; $j <= $len2; $j++) {
        $dp[0][$j] = $dp[0][$j - 1] && $s2[$j - 1] === $s3[$j - 1];
    }

    // 动态规划填表
    for ($i = 1; $i <= $len1; $i++) {
        for ($j = 1; $j <= $len2; $j++) {
            $dp[$i][$j] = ($dp[$i - 1][$j] && $s1[$i - 1] === $s3[$i + $j - 1]) ||
                          ($dp[$i][$j - 1] && $s2[$j - 1] === $s3[$i + $j - 1]);
        }
    }

    return $dp[$len1][$len2];
}

// 测试
echo isInterleave("aab", "xyb", "aaxyb") ? "true" : "false"; // 输出 true

Python 示例代码

def isInterleave(s1: str, s2: str, s3: str) -> bool:
    len1, len2, len3 = len(s1), len(s2), len(s3)
    if len1 + len2 != len3:
        return False

    dp = [[False] * (len2 + 1) for _ in range(len1 + 1)]
    dp[0][0] = True

    # 初始化第一行和第一列
    for i in range(1, len1 + 1):
        dp[i][0] = dp[i - 1][0] and s1[i - 1] == s3[i - 1]
    for j in range(1, len2 + 1):
        dp[0][j] = dp[0][j - 1] and s2[j - 1] == s3[j - 1]

    # 动态规划填表
    for i in range(1, len1 + 1):
        for j in range(1, len2 + 1):
            dp[i][j] = (dp[i - 1][j] and s1[i - 1] == s3[i + j - 1]) or \
                       (dp[i][j - 1] and s2[j - 1] == s3[i + j - 1])

    return dp[len1][len2]

# 测试
print(isInterleave("aab", "xyb", "aaxyb"))  # 输出 True

JavaScript 示例代码

function isInterleave(s1, s2, s3) {
    const len1 = s1.length;
    const len2 = s2.length;
    const len3 = s3.length;

    if (len1 + len2 !== len3) {
        return false;
    }

    const dp = Array.from({ length: len1 + 1 }, () => Array(len2 + 1).fill(false));
    dp[0][0] = true;

    // 初始化第一行和第一列
    for (let i = 1; i <= len1; i++) {
        dp[i][0] = dp[i - 1][0] && s1[i - 1] === s3[i - 1];
    }
    for (let j = 1; j <= len2; j++) {
        dp[0][j] = dp[0][j - 1] && s2[j - 1] === s3[j - 1];
    }

    // 动态规划填表
    for (let i = 1; i <= len1; i++) {
        for (let j = 1; j <= len2; j++) {
            dp[i][j] = (dp[i - 1][j] && s1[i - 1] === s3[i + j - 1]) ||
                       (dp[i][j - 1] && s2[j - 1] === s3[i + j - 1]);
        }
    }

    return dp[len1][len2];
}

// 测试
console.log(isInterleave("aab", "xyb", "aaxyb")); // 输出 true

这些示例代码都使用了动态规划的思想来解决交错字符串的问题，并提供了 PHP、Python 和 JavaScript 三种语言的实现。