当前位置： 面试刷题>> 交叉字符串 (经典算法题500道)
### 完整题目描述
**题目：交叉字符串**
给定两个字符串 `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 示例代码
```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 示例代码
```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 示例代码
```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));
```
**码小课**：在码小课网站上，你可以找到更多关于算法和数据结构的学习资源，帮助你深入理解和应用这些技术。通过实践和不断的学习，你将能够更熟练地解决各种编程问题。