LeetCode 30. 串联所有单词的子串

2025-04-17 HGNULB 约 7 分钟

文章信息 10 个分类 3 个标签

分类

LeetCode CodeTop 困难未解决 5-10 字节跳动阿里巴巴华为虾皮面试经典 150 题

题目描述

✅ 30. 串联所有单词的子串

题意分析

给定一个字符串和一组单词，要找出字符串中所有这样的起点：从该起点开始的一段连续子串，恰好是把这组单词全部各用一次、以任意顺序首尾相接拼出来的。返回所有起点，顺序不限。

题目给了一个极强的条件：所有单词长度完全相同。这意味着待匹配子串的长度是固定的，等于单词长度乘以单词个数；更重要的是，这段子串的内部切分点也是固定的——从起点开始每隔一个单词长度切一刀，切出来的每一块都必须恰好是某个单词，不存在跨越边界的匹配。

单词组里允许出现重复，所以判断依据不是「这些单词都出现过」而是「每个单词出现的次数分别对上」，必须用计数而非集合。

数据范围里字符串长度可到 $10^4$，单词个数可到 $5000$，单词长度不超过 $30$。这说明「枚举每个起点再逐块比对」这种 $O(n \cdot m)$ 的做法在最坏情形下会很吃力，需要让相邻起点之间复用已有的统计结果。

边界情形包括：字符串比目标子串还短，此时无解；单词组里全是同一个单词；字符串中出现了不属于单词组的块，它会切断所有跨越它的候选；以及答案起点可能相邻出现（比如单词全相同时，连续多个位置都合法）。

解法：按单词长度分组的滑动窗口

核心思路

所有单词等长，设长度为 $L$。合法子串从起点开始，每隔 $L$ 个字符切出一个单词，因此起点相差 $L$ 的候选拥有相同的切分边界；起点模 $L$ 不同的候选互不对齐。

枚举 offset = 0 ... L-1，每个偏移内以“一个单词”为单位滑动窗口。窗口维护：

need：目标中每个单词需要出现的次数；

window：当前窗口中的次数；

used：窗口包含的单词总数。

加入一个合法单词后，若它的次数超过需求，就从左侧逐词移出，直到频次恢复合法。此时所有单词都不超量；若 used 又恰好等于单词总数，则每个词频必然全部匹配，当前左端就是答案。

遇到不在 need 中的词块时，任何跨过它的窗口都不可能合法，直接清空状态并从下一块重新开始。

解题步骤

统计 words 的目标词频，并计算单词长度与单词总数。

对每个余数类分别初始化窗口，从 offset 开始每次右移 $L$。

当前词不在目标中时，清空窗口并把左端移到该词之后。

否则加入当前词；若该词超量，持续弹出左端词。

used == words.length 时记录左端。随后主动弹出一个左端词，以继续寻找重叠答案。

扫描完全部余数类后返回所有起点。

例如 s = "barfoofoo"、words = ["bar","foo"]：窗口先得到 bar,foo，记录起点 0；再加入第二个 foo 时会收缩到只剩该 foo，不会错误保留超量单词。

代码实现

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

class Solution {
    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> answer = new ArrayList<>();
        if (words.length == 0) {
            return answer;
        }

        int wordLength = words[0].length();
        int wordCount = words.length;
        if (s.length() < wordLength * wordCount) {
            return answer;
        }

        Map<String, Integer> need = new HashMap<>();
        for (String word : words) {
            need.put(word, need.getOrDefault(word, 0) + 1);
        }

        for (int offset = 0; offset < wordLength; offset++) {
            Map<String, Integer> window = new HashMap<>();
            int left = offset;
            int used = 0;

            for (int right = offset;
                    right + wordLength <= s.length();
                    right += wordLength) {
                String word = s.substring(right, right + wordLength);
                if (!need.containsKey(word)) {
                    window.clear();
                    used = 0;
                    left = right + wordLength;
                    continue;
                }

                window.put(word, window.getOrDefault(word, 0) + 1);
                used++;
                while (window.get(word) > need.get(word)) {
                    String removed = s.substring(left, left + wordLength);
                    window.put(removed, window.get(removed) - 1);
                    left += wordLength;
                    used--;
                }

                if (used == wordCount) {
                    answer.add(left);
                    String removed = s.substring(left, left + wordLength);
                    window.put(removed, window.get(removed) - 1);
                    left += wordLength;
                    used--;
                }
            }
        }
        return answer;
    }
}

func findSubstring(s string, words []string) []int {
    answer := make([]int, 0)
    if len(words) == 0 {
        return answer
    }

    wordLength := len(words[0])
    wordCount := len(words)
    if len(s) < wordLength*wordCount {
        return answer
    }

    need := make(map[string]int)
    for _, word := range words {
        need[word]++
    }

    for offset := 0; offset < wordLength; offset++ {
        window := make(map[string]int)
        left, used := offset, 0

        for right := offset; right+wordLength <= len(s); right += wordLength {
            word := s[right : right+wordLength]
            if _, ok := need[word]; !ok {
                clear(window)
                left = right + wordLength
                used = 0
                continue
            }

            window[word]++
            used++
            for window[word] > need[word] {
                removed := s[left : left+wordLength]
                window[removed]--
                left += wordLength
                used--
            }

            if used == wordCount {
                answer = append(answer, left)
                removed := s[left : left+wordLength]
                window[removed]--
                left += wordLength
                used--
            }
        }
    }
    return answer
}

复杂度分析

设字符串长度为 $n$、单词数为 $m$、单词长度为 $L$。

时间复杂度：$O((n+m)L)$。所有余数类合计处理 $O(n)$ 个词块，每个词块至多进窗、出窗各一次；截取和哈希长度为 $L$ 的单词需要 $O(L)$。

空间复杂度：$O(mL)$，两张词频表最多保存 $m$ 个长度为 $L$ 的不同单词；返回结果不计入额外空间。

关键点总结

等长单词使切分边界固定，按起点模 $L$ 分组后才能复用窗口。

重复单词要求维护词频，集合无法表达需求次数。

“所有词频不超量 + 窗口词数等于 $m$”即可推出词频完全一致。

非目标词触发整窗重置，目标词超量只需从左侧收缩。

记录答案后弹出一个词，才能自然继续寻找重叠解。

易错点总结

只扫描 offset = 0：会漏掉起点不被 $L$ 整除的答案。

用集合代替词频表：words = ["a","a"] 时无法判断重复次数。

遇到非法词后只移动左端、不清空计数：窗口状态会与实际区间脱节。

收缩时忘记同步减少 used：可能产生长度不正确的假答案。

子串右端没有检查 right + wordLength <= s.length()：末尾会越界。

相似题目

题目	难度	考察点
438. 找到字符串中所有字母异位词	中等	匹配单位退化为单个字符，窗口定长且逐字符滑动，无需按余数分类
567. 字符串的排列	中等	与 438 同构但只需判断是否存在，可在找到首个匹配时提前返回
76. 最小覆盖子串	困难	只要求覆盖而非恰好用完，窗口可变长且目标是最短，收缩条件相反
3. 无重复字符的最长子串	中等	约束是窗口内不重复，收缩由重复字符驱动，不涉及目标计数表
209. 长度最小的子数组	中等	窗口状态是数值和而非计数表，靠单调性保证每个元素只进出一次
239. 滑动窗口最大值	困难	定长窗口但维护的是极值，需要单调队列而不是哈希计数