串联所有单词的子串
在 LeetCode 上查看 ↗语音讲解
开车或通勤时可听，跟着思路走一遍
题目描述
给定一个字符串 s 和一个字符串数组 words。words 中所有字符串 长度相同。
s 中的 串联子串 是指一个包含 words 中所有字符串以任意顺序排列连接起来的子串。
返回所有串联子串在 s 中的开始索引。你可以以 任意顺序 返回答案。
示例 1
示例 2
示例 3
模拟答题者思考
1. 我先想暴力：枚举 s 中每个起点 i，切出长度 wordLen × |words| 的子串，再判断是否等于 words 的某种排列——要检查所有排列或逐词匹配，复杂度爆炸。
2. 重复在哪里？每个起点都在重新切词、重新比对。其实合法串联子串的长度固定，且每个单词长度相同，可以按「单词块」而不是单字符来滑窗。
3. 关键观察：若按字符下标 i 切块，只有 i % wordLen 相同的起点才属于同一套切分方式。所以对 offset = 0..wordLen-1 各跑一遍滑窗即可覆盖全部可能。
4. 滑窗逻辑类似「最小覆盖子串」：右扩加入一块单词，若某词超量就从左缩；当 valid == len(need) 时，left 即为一个合法串联子串起点。
5. 若右端切出的块不在 need 中，当前切分方式已不可能继续匹配，直接清空窗口并把 left 跳到 right 之后。
变量语义（先读这三句再编码）
| 变量 | 类型 | 语义（三句法） |
|---|---|---|
need[w] | map<string,int> | 定义：目标单词 w 在 words 中应出现的次数 维护：不变量，由 words 初始化 更新：不更新 |
window[w] | map<string,int> | 定义：当前「按单词切分」的滑窗内，单词 w 的出现次数 维护：随窗口在 s 上按 wordLen 步长滑动而增减更新：右端加入单词时 window[w]++；左端移出时 window[w]-- |
valid | int | 定义：窗口内已「恰好匹配」need 的单词种类数（window[w] == need[w]）维护：每轮后 valid 等于满足精确匹配的单词种类数 更新：某词计数从 need-1 变 need 时 valid++；从 need 变 need-1 时 valid-- |
offset | int | 定义：当前滑窗在 s 上的起始对齐偏移（0 到 wordLen-1） 维护：每个 offset 独立跑一遍「按单词步长」的滑窗，覆盖所有可能切分 更新：外层循环 offset++，内层从 offset 起按 wordLen 步进 |
left / right | int | 定义：当前窗口在 s 中的左右边界（字符下标） 维护：窗口始终覆盖连续 k 个单词块，总字符长 k × wordLen更新： right 每次 +wordLen 加入一块；超限时 left 循环 +wordLen 移出 |
落码步骤
1. 若 words 为空或 len(s) < wordLen × wordCount，直接返回空列表
2. 统计 need：遍历 words，need[w]++；记 wordLen、wordCount
3. 对每个 offset ∈ [0, wordLen)：初始化 left = offset、window = {}、valid = 0
4. right 从 offset 起每次 +wordLen：切出 word = s[right:right+wordLen]
5. 若 word 不在 need：清空 window、valid=0，left = right + wordLen（整块对齐后重启）
6. 否则 window[word]++，循环收缩：若 window[word] > need[word]，移出 left 块并更新 valid，left += wordLen
7. 若 window[word] == need[word] 则 valid++；当 valid == len(need) 时把 left 记入结果
8. 汇总所有 offset 的结果并返回
代码实现
class Solution:
def findSubstring(self, s: str, words: list[str]) -> list[int]:
if not words:
return []
word_len = len(words[0])
word_count = len(words)
total_len = word_len * word_count
if len(s) < total_len:
return []
need = {}
for w in words:
need[w] = need.get(w, 0) + 1
result = []
need_types = len(need)
for offset in range(word_len):
left = offset
valid = 0
window = {}
right = offset
while right + word_len <= len(s):
word = s[right:right + word_len]
if word not in need:
window.clear()
valid = 0
left = right + word_len
else:
window[word] = window.get(word, 0) + 1
while window[word] > need[word]:
left_word = s[left:left + word_len]
if window[left_word] == need[left_word]:
valid -= 1
window[left_word] -= 1
left += word_len
if window[word] == need[word]:
valid += 1
if valid == need_types:
result.append(left)
right += word_len
return resultclass Solution {
public:
vector<int> findSubstring(string s, vector<string>& words) {
vector<int> result;
if (words.empty()) return result;
int wordLen = words[0].size();
int wordCount = words.size();
int totalLen = wordLen * wordCount;
if (s.size() < totalLen) return result;
unordered_map<string, int> need;
for (const string& w : words) need[w]++;
int needTypes = need.size();
for (int offset = 0; offset < wordLen; offset++) {
int left = offset, valid = 0;
unordered_map<string, int> window;
for (int right = offset; right + wordLen <= s.size(); right += wordLen) {
string word = s.substr(right, wordLen);
if (!need.count(word)) {
window.clear();
valid = 0;
left = right + wordLen;
} else {
window[word]++;
while (window[word] > need[word]) {
string leftWord = s.substr(left, wordLen);
if (window[leftWord] == need[leftWord]) valid--;
window[leftWord]--;
left += wordLen;
}
if (window[word] == need[word]) valid++;
if (valid == needTypes) result.push_back(left);
}
}
}
return result;
}
};
// 时间 O(n × wordLen)，空间 O(m)复杂度分析
O(n × wordLen)
O(m)
常见坑
必须对每个 offset ∈ [0, wordLen) 单独滑窗；只从 0 开始会漏掉如 "barfoo" 与 "foobar" 这类不同对齐的合法起点。
valid 只在 window[w] == need[w] 时 +1，超过 need 不算；收缩时须先判断 == need 再 --，与最小覆盖子串一致。
遇到不在 need 中的单词块要整块重置窗口，并把 left 跳到 right+wordLen，否则脏数据会误报合法起点。
必测边界 Case
words = ["word","good","best","word"]，需要窗口内 "word" 恰好出现 2 次才算 valid。
len(s) < wordLen × wordCount → []（无需进入滑窗）
words = [] → []（按题意通常不会出现，但实现上应直接返回）