完整题目描述

题目：交叉字符串

给定两个字符串 s1 和 s2，判断是否存在一种方式，可以交替地从 s1 和 s2 中各取一个字符，最后形成一个新的字符串，该字符串同时是 s1 和 s2 的子序列。如果可以，则返回 true；否则返回 false。

注意：

• 子序列是指一个字符串删除某些（也可以不删除）字符后不改变剩余字符相对位置得到的新字符串。
• 交替取字符意味着，首先取 s1 的一个字符（如果可选），然后取 s2 的一个字符（如果可选），再取 s1 的一个字符（如果可选），以此类推，直到两个字符串都被取完或者无法继续取字符。

示例

示例 1:

输入: s1 = "aabcc", s2 = "dbbca"
输出: true
解释: 可以交替地从 s1 和 s2 中取字符得到 "aadbbcbcac"，这是 s1 和 s2 的子序列。

示例 2:

输入: s1 = "aabcc", s2 = "dbbcaa"
输出: false

PHP 示例代码

function isInterleave(string $s1, string $s2, string $s3) {
    $len1 = strlen($s1);
    $len2 = strlen($s2);
    $len3 = strlen($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++) {
        if ($s1[$i - 1] == $s3[$i - 1] && $dp[$i - 1][0]) {
            $dp[$i][0] = true;
        }
    }

    for ($j = 1; $j <= $len2; $j++) {
        if ($s2[$j - 1] == $s3[$j - 1] && $dp[0][$j - 1]) {
            $dp[0][$j] = true;
        }
    }

    for ($i = 1; $i <= $len1; $i++) {
        for ($j = 1; $j <= $len2; $j++) {
            if (($s1[$i - 1] == $s3[$i + $j - 1] && $dp[$i - 1][$j]) || 
                ($s2[$j - 1] == $s3[$i + $j - 1] && $dp[$i][$j - 1])) {
                $dp[$i][$j] = true;
            }
        }
    }

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

// 使用示例
$s1 = "aabcc";
$s2 = "dbbca";
$s3 = "aadbbcbcac";
echo isInterleave($s1, $s2, $s3) ? "true" : "false";

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):
        if s1[i - 1] == s3[i - 1] and dp[i - 1][0]:
            dp[i][0] = True

    for j in range(1, len2 + 1):
        if s2[j - 1] == s3[j - 1] and dp[0][j - 1]:
            dp[0][j] = True

    for i in range(1, len1 + 1):
        for j in range(1, len2 + 1):
            if (s1[i - 1] == s3[i + j - 1] and dp[i - 1][j]) or \
               (s2[j - 1] == s3[i + j - 1] and dp[i][j - 1]):
                dp[i][j] = True

    return dp[len1][len2]

# 使用示例
s1 = "aabcc"
s2 = "dbbca"
s3 = "aadbbcbcac"
print(isInterleave(s1, s2, s3))

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++) {
        if (s1[i - 1] === s3[i - 1] && dp[i - 1][0]) {
            dp[i][0] = true;
        }
    }

    for (let j = 1; j <= len2; j++) {
        if (s2[j - 1] === s3[j - 1] && dp[0][j - 1]) {
            dp[0][j] = true;
        }
    }

    for (let i = 1; i <= len1; i++) {
        for (let j = 1; j <= len2; j++) {
            if ((s1[i - 1] === s3[i + j - 1] && dp[i - 1][j]) ||
                (s2[j - 1] === s3[i + j - 1] && dp[i][j - 1])) {
                dp[i][j] = true;
            }
        }
    }

    return dp[len1][len2];
}

// 使用示例
const s1 = "aabcc";
const s2 = "dbbca";
const s3 = "aadbbcbcac";
console.log(isInterleave(s1, s2, s3));

码小课：在码小课网站上，你可以找到更多关于算法和数据结构的学习资源，帮助你深入理解和应用这些技术。通过实践和不断的学习，你将能够更熟练地解决各种编程问题。