查找字符串中含指定单词数组全排列的起始下标及算法优化咨询

问题需求 #

查找字符串中所有包含给定单词数组所有单词的任意排列组合的起始下标。

示例数据 #

• 输入字符串："barfoofoobarthefoobarman"
• 输入单词数组：["bar", "foo", "the"]
• 正确输出：[6, 9, 12]

原有暴力解法的缺陷 #

你之前实现的版本存在两个核心问题：

1. 遍历起始下标的步长固定为单词长度，会漏掉所有起始下标不是单词长度整数倍的符合条件的结果
2. 每次遍历都需要完整复制原始单词计数Map、完整遍历整个待匹配子串统计，大量重复操作导致性能极低，无法适配长字符串、大单词数组的场景

优化方案：滑动窗口法 #

核心思路 #

因为题目默认所有单词长度相同，我们可以按偏移量拆分遍历分组（共「单词长度」个分组），每个分组内部使用滑动窗口扫描，仅在窗口滑动时更新计数，避免重复统计，时间复杂度可以降到O(n)，n为输入字符串长度。

实现代码 #

var solution = function(s, words) {
    const res = [];
    const wordLen = words[0].length;
    const wordCount = words.length;
    const totalLen = wordLen * wordCount;
    // 构建原始单词计数Map
    const originMap = new Map();
    for (const word of words) {
        originMap.set(word, (originMap.get(word) || 0) + 1);
    }
    // 按偏移量分组遍历
    for (let offset = 0; offset < wordLen; offset++) {
        let left = offset;
        let right = offset;
        let matched = 0;
        const windowMap = new Map();
        // 窗口右边界不超出字符串长度
        while (right + wordLen <= s.length) {
            const curWord = s.slice(right, right + wordLen);
            right += wordLen;
            // 当前单词在原始列表中，更新窗口计数
            if (originMap.has(curWord)) {
                windowMap.set(curWord, (windowMap.get(curWord) || 0) + 1);
                // 该单词计数刚好匹配，匹配数+1
                if (windowMap.get(curWord) === originMap.get(curWord)) {
                    matched++;
                }
            }
            // 窗口长度超过总匹配长度，移动左边界缩小窗口
            while (right - left > totalLen) {
                const leftWord = s.slice(left, left + wordLen);
                left += wordLen;
                if (originMap.has(leftWord)) {
                    // 该单词计数之前刚好匹配，现在移出后匹配数-1
                    if (windowMap.get(leftWord) === originMap.get(leftWord)) {
                        matched--;
                    }
                    windowMap.set(leftWord, windowMap.get(leftWord) - 1);
                }
            }
            // 所有单词都匹配，记录起始下标
            if (matched === originMap.size) {
                res.push(left);
            }
        }
    }
    return res;
}
// 测试
console.log(solution("barfoofoobarthefoobarman", ["bar", "foo", "the"])); // 输出 [6,9,12]

优势说明 #

• 没有重复的Map复制和全子串遍历操作，仅在窗口滑动时做O(1)的计数更新
• 覆盖所有可能的起始下标，不会遗漏结果
• 时间复杂度比原有暴力解法降低一个数量级，适配大规模输入场景

内容的提问来源于stack exchange，提问作者Luis Carlos García