LeetCode 30. 串联所有单词的子串
题目描述
题意分析
在字符串
s中找出所有符合条件的连续子串：它们恰好由words中的全部单词按某种顺序直接连接而成。每次出现都必须使用一次，单词之间不能夹杂其他字符，返回这些子串的起始下标，答案顺序不限。所有单词长度相同。若词长为
L、单词总数为m，答案子串长度就固定为m * L。单词可以重复，因此需要匹配每个词的出现次数；不同答案可以重叠，不能找到一个后就跳过整段。
解法：按单词长度分组的滑动窗口
核心思路
[!blue]
等长单词让切分边界固定。一个合法起点确定后，后面的词块都间隔
L个字符。将起点按除以L的余数分成L组，对每个offset独立扫描完整词块，就能像按字符滑动一样复用窗口，同时覆盖所有可能的起始下标。
need保存每个目标单词需要出现多少次，window保存当前窗口的词频，left是窗口起点，used是窗口中的词块数量。右端每次加入一个长度为L的新词，窗口保持连续，左端也只能按整词移动。若新词不在目标词表中，任何跨过这个词块的候选都不可能合法。将窗口替换为空计数表，令
used = 0，并把left移到该词之后，重新开始扫描。这里重新创建空表，不反复清理旧表保留的大容量，避免曾经扩大的窗口给后续每次重置带来额外扫描。若新词属于目标，先增加它的计数与
used。此前所有词频都不超额，所以此时只有刚加入的这个词可能超额；只要它的次数仍高于需求，就持续移出左端词，并同步更新计数、left和used，直到恢复合法数量范围。被移出的前缀不可能构成以当前右端结束的合法答案，因为它仍包含超额的词。恢复之后，窗口里每种词的数量都不超过需求。若总词数又恰好等于
m，所有需求之和已被填满，就能推出每种词的次数都恰好匹配，记录left即可，无需再遍历整张词频表比较。记录答案后只移出最左的一个词，再继续读取后面的词块。这样下一个窗口仍能复用已匹配的后缀，不会丢失重叠答案。每个偏移组都独立维护计数，最终汇总全部起点。
解题步骤
- 统计
words中每个词的需求次数；若文本不足总长度，直接返回空结果。- 枚举
offset = 0..L - 1，从该起点创建独立窗口，每次右移一个词长。- 遇到非目标词时重建空窗口，并把左端放到该词之后。
- 遇到目标词时加入窗口；若刚加入的词超额，就逐词移出左端，直到次数合法。
used == m时记录左端起点，再移出一个左端词，继续搜索重叠结果。- 所有偏移组结束后返回答案。
代码实现
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 = new HashMap<>();
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 {
// 非目标词切断当前候选，计数、词数和左边界必须一起重置。
window = make(map[string]int)
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)$。构造需求表需处理
m个词；所有偏移组共扫描 $O(n)$ 个词块，每块至多入窗、出窗各一次，截取或哈希词块最多需要 $O(L)$。重置使用新空表，不扫描旧表的历史容量。- 空间复杂度：$O(mL)$，需求表与当前窗口最多保存
m种目标词及次数，不计返回结果。
关键点总结
[!green]
- 按词长余数分组，让同一组的窗口始终以完整单词为单位移动。
- 非目标词切断整段候选，目标词超额只需要删除窗口前缀。
- 所有词频不超额且总词数恰好够用，就等价于完整频次匹配。
易错点总结
[!yellow]
- 只扫描从零开始的一组，会漏掉其他切词边界对应的答案。
- 用集合代替词频表，无法表达同一单词需要多次出现的情况。
- 遇到非目标词时只移动左端，却保留旧计数或旧
used，会使状态与实际窗口脱节。- 用一次
if收缩代替while，可能尚未移出旧的超额词，就继续接受错误窗口。- 移出左端词时忘记递减
used，会把不足指定长度的窗口误认为完整串联。- 记录答案后跳过整个窗口，会漏掉与当前答案重叠的起点；这里只移出一个词。
- 读取词块前没有检查
right + L <= s.length()，会在文本尾部截取越界。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 438. 找到字符串中所有字母异位词 | 中等 | 同样用定长窗口比较频次，本题窗口单位是等长单词，需要按单词长度分别扫描偏移。 |
| 76. 最小覆盖子串 | 困难 | 同样维护需求计数，原题允许任意长度的覆盖窗口，本题串联长度由词数和词长固定。 |