京公网安备11010502063487号给定一个字符串 s 和一组长度相同的单词，找出 s 中所有的子串起点：从该起点开始的一段，恰好是这组单词以任意顺序拼接起来的结果（每个单词恰好用一次）。暴力做法是对每个起点，把接下来的一段切成单词，和给定的单词组比较，时间约 O(n · m · w)（m 是单词个数，w 是单词长度）。因为所有单词长度相同，可以把 s 按"单词"为单位滑动窗口：只需要从 w 个不同的偏移出发各做一遍窗口，每一遍里每个单词只进出窗口一次。本文用真实数据展示"用集合代替计数"这一常见的错误，实测两种做法的耗时，给出五种语言的实现，并把滑动窗口的过程做成分步演示。
完整题目见官方页面（链接在文末）。单词可以重复，所以要按"每个单词出现几次"来核对，不能只看有哪些单词。基准解是暴力做法：每个起点切成 m 段，排序后与排序后的单词组比较；这是最直观、最容易确认正确性的写法。结果的起点顺序不作要求，按集合比较。一共 12 组用例，覆盖：官方示例、单词重复、没有匹配、单字符单词、s 为空：
输入 ["barfoothefoobarman",["foo","bar"]] 输出 [0,9] 输入 ["wordgoodgoodgoodbestword",["word","good","best","word"]] 输出 [] 输入 ["barfoofoobarthefoobarman",["bar","foo","the"]] 输出 [6,9,12] 输入 ["lingmindraboofooowingdingbarrwingmonkeypoundcake",["fooo","barr","wing","ding","wing"]] 输出 [13] 输入 ["aaaaaaaa",["aa","aa","aa"]] 输出 [0,1,2] 输入 ["a",["a"]] 输出 [0]
单词组里可能有重复的单词，例如 ["word", "good", "best", "word"]，这里 word 要出现两次。如果只用集合判断"窗口里的单词种类和单词组一样"，就会漏掉数量的检查。下面是这种写法与 solve 的真实结果：
# 用集合代替计数的写法 s='wordgoodgoodgoodbestword', words=['word', 'good', 'best', 'word']: 用集合 -> [8] solve -> [] s='aaaa', words=['a', 'a']: 用集合 -> [0, 1, 2] solve -> [0, 1, 2] s='ababab', words=['ab', 'ab', 'ab']: 用集合 -> [0] solve -> [0] s='abab', words=['ab', 'ab']: 用集合 -> [0] solve -> [0]
第一行：官方的第二个示例里，s 中 word 只出现在头和尾，用集合的写法在下标 8 处找到了一个"匹配"：那一段切成 good、good、best、word，单词种类是齐全的，但单词组要求 word 出现两次、good 一次，而这一段是 good 两次、word 一次，并不是这组单词的一个排列，所以正确答案是空。后面几行数据里所有的单词种类都只有一种，所以集合和计数两种写法结果相同，这个错误只在单词有重复、且种类数与单词个数不一致时才暴露。
先统计单词组里每个单词需要出现几次（need）。对每一个偏移 off（0 到 w-1），从 off 开始每次向右跳 w 个字符，取一个单词：如果这个单词不在单词组里，窗口整个作废，从下一个位置重新开始；否则把它加入窗口，如果它的个数超过了需要的个数，就从左边移出单词，直到不超为止；当窗口里正好有 m 个单词，因为每个单词都不超过需要的个数，所以恰好等于单词组，记录起点，然后再从左边移出一个单词继续滑动。Python、Java、Go、JavaScript、C++ 都是真实编译运行的。
Python · 解法代码def solve(s, words): if not s or not words: return [] w, m = len(words[0]), len(words) need = Counter(words) res = [] for off in range(w): # 单词长度都是 w：只需要分别从 0..w-1 这 w 个偏移出发，各做一次滑动窗口 left, cnt, win = off, 0, {} for right in range(off, len(s) - w + 1, w): word = s[right:right + w] if word not in need: # 遇到不在列表里的单词：窗口整个作废 win.clear() cnt = 0 left = right + w continue win[word] = win.get(word, 0) + 1 cnt += 1 while win[word] > need[word]: # 某个单词多了：左边收缩，直到不多为止 lw = s[left:left + w] win[lw] -= 1 cnt -= 1 left += w if cnt == m: # 窗口里恰好是 m 个单词，且每个单词的数量都不超过需要的 => 恰好匹配 res.append(left) lw = s[left:left + w] win[lw] -= 1 cnt -= 1 left += w return res
$ python3 solution.py # 统一入口：逐行读取 cases.jsonl，调用上面的 solve，打印 JSON ["barfoothefoobarman",["foo","bar"]] → [0,9] ["wordgoodgoodgoodbestword",["word","good","best","word"]] → [] ["barfoofoobarthefoobarman",["bar","foo","the"]] → [6,9,12] ["lingmindraboofooowingdingbarrwingmonkeypoundcake",["fooo","barr","wing","ding","wing"]] → [13] ["aaaaaaaa",["aa","aa","aa"]] → [0,2,1] ["a",["a"]] → [0]
Java · 解法代码class Solution { public List<Integer> findSubstring(String s, String[] words) { List<Integer> res = new ArrayList<>(); if (s.isEmpty() || words.length == 0) return res; int w = words[0].length(), m = words.length; Map<String, Integer> need = new HashMap<>(); for (String x : words) need.merge(x, 1, Integer::sum); for (int off = 0; off < w; off++) { // 单词长度都是 w：只需要分别从 0..w-1 这 w 个偏移出发 int left = off, cnt = 0; Map<String, Integer> win = new HashMap<>(); for (int right = off; right + w <= s.length(); right += w) { String word = s.substring(right, right + w); if (!need.containsKey(word)) { // 遇到不在列表里的单词：窗口整个作废 win.clear(); cnt = 0; left = right + w; continue; } win.merge(word, 1, Integer::sum); cnt++; while (win.get(word) > need.get(word)) { // 某个单词多了：左边收缩 String lw = s.substring(left, left + w); win.merge(lw, -1, Integer::sum); cnt--; left += w; } if (cnt == m) { // 恰好 m 个单词且每个都不多 => 匹配 res.add(left); String lw = s.substring(left, left + w); win.merge(lw, -1, Integer::sum); cnt--; left += w; } } } return res; } }
$ javac -d build Main.java Solution.java && java -cp build Main < cases.jsonl ["barfoothefoobarman",["foo","bar"]] → [0,9] ["wordgoodgoodgoodbestword",["word","good","best","word"]] → [] ["barfoofoobarthefoobarman",["bar","foo","the"]] → [6,9,12] ["lingmindraboofooowingdingbarrwingmonkeypoundcake",["fooo","barr","wing","ding","wing"]] → [13] ["aaaaaaaa",["aa","aa","aa"]] → [0,2,1] ["a",["a"]] → [0]
Go · 解法代码func findSubstring(s string, words []string) []int { res := []int{} if len(s) == 0 || len(words) == 0 { return res } w, m := len(words[0]), len(words) need := map[string]int{} for _, x := range words { need[x]++ } for off := 0; off < w; off++ { // 单词长度都是 w：只需要分别从 0..w-1 这 w 个偏移出发 left, cnt := off, 0 win := map[string]int{} for right := off; right+w <= len(s); right += w { word := s[right : right+w] if _, ok := need[word]; !ok { // 遇到不在列表里的单词：窗口整个作废 win = map[string]int{} cnt = 0 left = right + w continue } win[word]++ cnt++ for win[word] > need[word] { // 某个单词多了：左边收缩 win[s[left:left+w]]-- cnt-- left += w } if cnt == m { // 恰好 m 个单词且每个都不多 => 匹配 res = append(res, left) win[s[left:left+w]]-- cnt-- left += w } } } return res }
$ go build -o bin . && ./bin < cases.jsonl ["barfoothefoobarman",["foo","bar"]] → [0,9] ["wordgoodgoodgoodbestword",["word","good","best","word"]] → [] ["barfoofoobarthefoobarman",["bar","foo","the"]] → [6,9,12] ["lingmindraboofooowingdingbarrwingmonkeypoundcake",["fooo","barr","wing","ding","wing"]] → [13] ["aaaaaaaa",["aa","aa","aa"]] → [0,2,1] ["a",["a"]] → [0]
JavaScript · 解法代码function findSubstring(s, words) { const res = []; if (s.length === 0 || words.length === 0) return res; const w = words[0].length, m = words.length; const need = new Map(); for (const x of words) need.set(x, (need.get(x) || 0) + 1); for (let off = 0; off < w; off++) { // 单词长度都是 w：只需要分别从 0..w-1 这 w 个偏移出发 let left = off, cnt = 0; const win = new Map(); for (let right = off; right + w <= s.length; right += w) { const word = s.substring(right, right + w); if (!need.has(word)) { // 遇到不在列表里的单词：窗口整个作废 win.clear(); cnt = 0; left = right + w; continue; } win.set(word, (win.get(word) || 0) + 1); cnt++; while (win.get(word) > need.get(word)) { // 某个单词多了：左边收缩 const lw = s.substring(left, left + w); win.set(lw, win.get(lw) - 1); cnt--; left += w; } if (cnt === m) { // 恰好 m 个单词且每个都不多 => 匹配 res.push(left); const lw = s.substring(left, left + w); win.set(lw, win.get(lw) - 1); cnt--; left += w; } } } return res; }
$ node run.js < cases.jsonl ["barfoothefoobarman",["foo","bar"]] → [0,9] ["wordgoodgoodgoodbestword",["word","good","best","word"]] → [] ["barfoofoobarthefoobarman",["bar","foo","the"]] → [6,9,12] ["lingmindraboofooowingdingbarrwingmonkeypoundcake",["fooo","barr","wing","ding","wing"]] → [13] ["aaaaaaaa",["aa","aa","aa"]] → [0,2,1] ["a",["a"]] → [0]
C++ · 解法代码#include <string> #include <unordered_map> #include <vector> using namespace std; class Solution { public: vector<int> findSubstring(string s, vector<string>& words) { vector<int> res; if (s.empty() || words.empty()) return res; int w = words[0].size(), m = words.size(), n = s.size(); unordered_map<string, int> need; for (auto& x : words) need[x]++; for (int off = 0; off < w; off++) { // 单词长度都是 w：只需要分别从 0..w-1 这 w 个偏移出发 int left = off, cnt = 0; unordered_map<string, int> win; for (int right = off; right + w <= n; right += w) { string word = s.substr(right, w); if (!need.count(word)) { // 遇到不在列表里的单词：窗口整个作废 win.clear(); cnt = 0; left = right + w; continue; } win[word]++; cnt++; while (win[word] > need[word]) { // 某个单词多了：左边收缩 win[s.substr(left, w)]--; cnt--; left += w; } if (cnt == m) { // 恰好 m 个单词且每个都不多 => 匹配 res.push_back(left); win[s.substr(left, w)]--; cnt--; left += w; } } } return res; } };
$ clang++ -std=c++17 -O2 -o bin sol.cpp && ./bin < cases.jsonl ["barfoothefoobarman",["foo","bar"]] → [0,9] ["wordgoodgoodgoodbestword",["word","good","best","word"]] → [] ["barfoofoobarthefoobarman",["bar","foo","the"]] → [6,9,12] ["lingmindraboofooowingdingbarrwingmonkeypoundcake",["fooo","barr","wing","ding","wing"]] → [13] ["aaaaaaaa",["aa","aa","aa"]] → [0,2,1] ["a",["a"]] → [0]
共 12 组用例（含边界），以暴力解的结果为基准逐组比对： Python 通过 12/12 Java 通过 12/12 Go 通过 12/12 JavaScript 通过 12/12 C++ 通过 12/12
s 的长度分别为 1000、2000、4000、8000，单词组是 100 个长度为 3 的单词（由 a、b、c 循环生成），每个规模取三次中最快的一次：
s 的长度（100 个长度 3 的单词） | 暴力解 | 本文解法
1000 | 9.228 ms | 0.163 ms
2000 | 22.318 ms | 0.331 ms
4000 | 48.619 ms | 0.670 ms
8000 | （未测，太慢） | 1.389 ms两种做法在这批数据上都随 s 的长度线性增长（长度每翻一倍，耗时大约翻一倍），但暴力解每个起点都要处理 100 个单词，所以慢得多：n = 4000 时暴力解 48.6ms，滑动窗口 0.67ms，约 73 倍。暴力解在 n = 8000 时没有再测。这批数据是我自己造的，结果的个数和匹配的密度会影响耗时，不同数据上的倍数可能不同。
Python 版本另外和暴力解做了随机对拍。字母表只有 a、b，单词长 1 到 2，这样单词重复得很多，最容易暴露计数的错误：
随机对拍 20000 组（字母表只有 a、b，单词长 1 到 2、个数 1 到 4（所以单词重复很多），s 长 0 到 16；结果按集合比较），solve 与 brute 的结果全部一致。
另外四种语言只在上面 12 组固定用例上验证过，没有做大规模随机对拍。
下面的演示用官方示例 s = "barfoothefoobarman"、words = ["foo", "bar"]。每个单词长 3，所以要从偏移 0、1、2 各做一遍。偏移 0 那一遍在下标 0 和 9 找到匹配；偏移 1 和 2 那两遍取出来的三个字符都不是 foo 或 bar，窗口一直被清空。每一帧都是把上面的解法在这组输入上真实执行记录下来的，运行器还检查了演示最终得到的起点集合与 solve 的返回值一致。