当前位置： 面试刷题>> 交错字符串(经典算法150题)
### 题目描述
**交错字符串**：给定三个字符串 `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 示例代码
```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 示例代码
```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 示例代码
```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 三种语言的实现。