当前位置： 面试刷题>> 子串字谜 (经典算法题500道)
**题目描述补充**：
题目名称：子串字谜（Substring Puzzle）
题目描述：给定一个字符串`s`和一个目标字符串`t`，请找出`s`中所有不同的子串（连续的子序列），这些子串经过重新排列后可以组成`t`。返回这些符合条件的子串的起始索引。注意，同一个起始索引只应被计算一次，即使它对应多个不同的子串排列可以组成`t`。
**示例**：
输入：
```
s = "abcdeba"
t = "abc"
```
输出：
```
[0, 1, 6]
```
解释：
- 索引0开始的子串"abc"可以直接组成"abc"。
- 索引1开始的子串"bcdea"包含"abc"作为其子序列的排列。
- 索引6开始的子串"abc"也可以直接组成"abc"。
注意，虽然索引5开始的子串"eba"包含"a", "b", "c"这些字符，但它们不能重新排列成"abc"，因此不被计入结果。
**PHP代码示例**：
```php
function findSubstringIndices($s, $t) {
$result = [];
$targetCounts = array_count_values(str_split($t));
$n = strlen($s);
$m = strlen($t);
for ($i = 0; $i <= $n - $m; $i++) {
$currentCounts = [];
for ($j = 0; $j < $m; $j++) {
$char = $s[$i + $j];
if (isset($currentCounts[$char])) {
$currentCounts[$char]++;
} else {
$currentCounts[$char] = 1;
}
}
if ($currentCounts == $targetCounts) {
$result[] = $i;
}
}
return $result;
}
// 示例
$s = "abcdeba";
$t = "abc";
$indices = findSubstringIndices($s, $t);
print_r($indices);
```
**注意**： 上述PHP代码示例未完全遵循题目要求，因为它检查的是子串的字符频率而非重新排列的可能性。完全符合题目要求的实现可能需要更复杂的逻辑，如使用回溯法或动态规划，但这会显著增加实现的复杂度。
**Python代码示例**：
Python的示例将更复杂，因为直接检查所有可能的子串排列效率很低。通常，可以使用哈希表来简化字符频率的检查，但完全验证所有可能的排列需要更高级的技术（如使用回溯或深度优先搜索）。
**JavaScript代码示例**：
JavaScript示例同样面临效率问题，这里提供一个简化的版本，仅检查字符频率：
```javascript
function findSubstringIndices(s, t) {
const targetCounts = {};
const result = [];
for (let char of t) {
targetCounts[char] = (targetCounts[char] || 0) + 1;
}
const n = s.length;
const m = t.length;
for (let i = 0; i <= n - m; i++) {
const currentCounts = {};
for (let j = 0; j < m; j++) {
const char = s[i + j];
if (currentCounts[char]) {
currentCounts[char]++;
} else {
currentCounts[char] = 1;
}
if (currentCounts[char] > targetCounts[char] || !targetCounts[char]) {
break; // 提前结束内层循环，因为当前子串不可能组成t
}
}
// 这里简化为只检查频率相等的情况，未进行全排列检查
if (Object.keys(currentCounts).length === Object.keys(targetCounts).length) {
let isValid = true;
for (let key in currentCounts) {
if (currentCounts[key] !== targetCounts[key]) {
isValid = false;
break;
}
}
if (isValid) {
result.push(i);
}
}
}
return result;
}
// 示例
const s = "abcdeba";
const t = "abc";
const indices = findSubstringIndices(s, t);
console.log(indices);
```
**注意**： 上述JavaScript代码示例也简化了问题，仅通过字符频率来检查，并未真正验证所有可能的子串排列。完全按照题目要求实现可能需要更复杂的算法。
**码小课提示**： 码小课网站中有更多关于字符串处理、算法和数据结构的相关内容分享，欢迎大家学习交流。