当前位置: 面试刷题>> 子串字谜 (经典算法题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代码示例

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示例同样面临效率问题,这里提供一个简化的版本,仅检查字符频率:

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代码示例也简化了问题,仅通过字符频率来检查,并未真正验证所有可能的子串排列。完全按照题目要求实现可能需要更复杂的算法。

码小课提示: 码小课网站中有更多关于字符串处理、算法和数据结构的相关内容分享,欢迎大家学习交流。

推荐面试题