0030. Substring with Concatenation of All Words¶
题目信息¶
- 题号:
串联所有单词的子串
- 难度:
Hard
- 主题:
字符串、哈希计数、滑动窗口
- 原题:
- 重点:
从逐起点重建词频,推导到按单词长度分组的滑动窗口,并处理重复单词与重叠答案
题目重述¶
给定字符串 s 和字符串数组 words。words 中所有单词长度相同。返回 s 中所有满足条件的零基起始
下标:从该位置开始的连续子串,可以由 words 中的全部单词各使用一次、按任意顺序首尾拼接而成。
设单词长度为 w、单词数量为 k,目标子串长度固定为 w * k。候选子串必须切成 k 个长度为
w 的块,每个单词的出现次数必须与 words 完全相同。不同答案允许重叠,返回顺序不限。
约束为 1 <= s.length <= 10^4、1 <= words.length <= 5000、
1 <= words[i].length <= 30,字符串只包含小写英文字母。
自建示例¶
s = "barfoofoofoobar"、words = ["bar", "foo", "foo"],返回[0, 6];s = "xbarfooend"、words = ["bar", "foo"],返回[1];s = "catdogcat"、words = ["cat", "dog"],返回[0, 3];s = "foofoobar"、words = ["foo", "bar", "bar"],返回[];s = "abc"、words = ["ab", "cd"],目标总长度超过文本,返回[]。
C++ 实现¶
#include <string>
#include <unordered_map>
#include <vector>
class Solution {
private:
std::unordered_map<std::string, int> buildRequirement(
const std::vector<std::string>& words
) {
std::unordered_map<std::string, int> requirement;
for (const std::string& word : words) {
++requirement[word];
}
return requirement;
}
std::vector<int> recountEveryStart(
const std::string& s,
const std::vector<std::string>& words
) {
std::vector<int> result;
if (words.empty()) {
return result;
}
const int wordLength = static_cast<int>(words.front().size());
const int wordCount = static_cast<int>(words.size());
const int totalLength = wordLength * wordCount;
if (totalLength > static_cast<int>(s.size())) {
return result;
}
const auto requirement = buildRequirement(words);
for (int start = 0;
start + totalLength <= static_cast<int>(s.size());
++start) {
std::unordered_map<std::string, int> used;
int block = 0;
for (; block < wordCount; ++block) {
const int position = start + block * wordLength;
const std::string word = s.substr(position, wordLength);
const auto required = requirement.find(word);
if (required == requirement.end()) {
break;
}
if (++used[word] > required->second) {
break;
}
}
if (block == wordCount) {
result.push_back(start);
}
}
return result;
}
std::vector<int> slidingByOffsets(
const std::string& s,
const std::vector<std::string>& words
) {
std::vector<int> result;
if (words.empty() || words.front().empty()) {
return result;
}
const int wordLength = static_cast<int>(words.front().size());
const int wordCount = static_cast<int>(words.size());
const int totalLength = wordLength * wordCount;
if (totalLength > static_cast<int>(s.size())) {
return result;
}
const auto requirement = buildRequirement(words);
for (int offset = 0; offset < wordLength; ++offset) {
int left = offset;
int windowWords = 0;
std::unordered_map<std::string, int> seen;
for (int right = offset;
right + wordLength <= static_cast<int>(s.size());
right += wordLength) {
const std::string word = s.substr(right, wordLength);
const auto required = requirement.find(word);
if (required == requirement.end()) {
seen.clear();
windowWords = 0;
left = right + wordLength;
continue;
}
++seen[word];
++windowWords;
while (seen[word] > required->second) {
const std::string removed = s.substr(left, wordLength);
--seen[removed];
--windowWords;
left += wordLength;
}
if (windowWords == wordCount) {
result.push_back(left);
const std::string removed = s.substr(left, wordLength);
--seen[removed];
--windowWords;
left += wordLength;
}
}
}
return result;
}
public:
std::vector<int> findSubstring(
std::string s,
std::vector<std::string>& words
) {
return slidingByOffsets(s, words);
}
};
题解¶
逐起点验证¶
目标子串长度固定为 L = w * k。最直接的方法枚举每个满足 start + L <= s.size() 的字符起点,再把
区间 [start, start + L) 按长度 w 切成 k 个块。
recountEveryStart 先建立需求词频 requirement。验证一个起点时,从左到右读取各块:当前块不在需求表中,
或使用次数超过需求时,候选立即失败;成功读取 k 个块时,当前起点就是答案。
每个候选的切分方式唯一,因此该方法不会漏解。瓶颈是每个起点都重新创建 used,并再次统计与相邻候选重叠的
单词块。
等长分块¶
窗口不能任意移动一个字符后直接复用词频,因为单词必须保持完整。答案起点又不一定是 w 的整数倍,例如
"xbarfooend" 中的答案从下标 1 开始。
按照起点除以 w 的余数,可以把所有块起点拆成 w 条扫描线:
偏移 0:0, w, 2w, ...
偏移 1:1, 1+w, 1+2w, ...
...
偏移 w-1:w-1, 2w-1, ...
同一候选中的全部单词块必定位于同一条扫描线。依次扫描所有偏移可以覆盖全部字符起点,每个完整块起点又只属于 其中一条扫描线。
窗口不变量¶
在一条扫描线上,right 每次前进 w 个字符,窗口维护:
left:窗口首块起点;seen[word]:窗口内各单词次数;windowWords:窗口块数。
每轮调整结束后保持两个条件:窗口只包含需求表中的单词,并且每种单词的次数都不超过需求。这样的窗口仍可能继续 扩展成完整答案。
非法块重置¶
若新块不在 requirement 中,任何跨过该块的候选都会包含一个多余单词。此时清空 seen,把
windowWords 设为零,并令 left 移到该块之后。
这一次重置同时排除了所有跨越该非法块的起点,避免逐起点方法反复遇到同一个失败原因。
超量收缩¶
加入一个需求单词后,只有该单词的次数可能超出上限。若 seen[word] > requirement[word],从左侧逐块移除,
直到它恢复到允许次数。
被删除的更早起点都不可能与当前右端组成答案,因为相应窗口包含过多的 word。其他单词在收缩时只会减少,
无需检查新的超量项。左边界始终单向前进,所以每个块最多被移出一次。
完整窗口¶
窗口调整后,各单词次数均不超过需求。若 windowWords == wordCount,窗口总次数已经等于需求总次数。
此时若某个单词次数仍小于需求,就必须有另一个单词次数大于需求才能补足总数,与窗口不变量矛盾。因此所有词频
必然逐项相等,left 就是合法起点,不需要再次比较整张哈希表。
重叠答案¶
记录答案后只移除最左单词块,不清空窗口。这样可以保留当前答案的后缀,继续发现与它重叠的下一答案。
对 s = "barfoofoofoobar"、words = ["bar", "foo", "foo"]:
bar, foo, foo -> 命中下标 0,移除 bar
foo, foo, foo -> foo 超量,移除最左 foo
foo, foo, bar -> 命中下标 6
若首次命中后清空窗口,后续仍可能重新找到下标 6,却会丢弃本来可以复用的两个 foo。
代码演进¶
recountEveryStart 对每个字符起点重新统计最多 k 个单词块。
等长条件把候选拆成按 start mod w 对齐的扫描线。slidingByOffsets 在每条扫描线上复用窗口:右端只加入
一个新块,左端只在非法块、超量单词或完整命中后向前移动。
公开入口采用对齐滑动窗口。它保留重复单词的精确频次,也不会遗漏不同偏移或彼此重叠的答案。
复杂度分析¶
设 n = s.size()、单词长度为 w、单词数量为 k、不同单词数为 u。
逐起点方法最多验证 n - wk + 1 个起点,每个起点检查至多 k 个块。按当前 substr 与字符串哈希实现,
字符级时间为 O((n - wk + 1)kw),局部计数表使用 O(u) 空间。
滑动窗口中,每个完整块最多从右端加入一次、从左端移除一次。所有偏移合计为 O(n) 次块处理;按当前字符串
切片实现,字符级时间为 O(nw)。需求表与窗口表最多保存 u 个单词,工作空间为 O(u)。