0030. Substring with Concatenation of All Words
===============================================
题目信息
--------
:题号: 0030. 串联所有单词的子串
:难度: Hard
:主题: 字符串、哈希计数、滑动窗口
:原题: `LeetCode 0030 `_
:重点: 从逐起点重建词频,推导到按单词长度分组的滑动窗口,并处理重复单词与重叠答案
题目重述
--------
给定字符串 ``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++ 实现
--------
.. code-block:: cpp
#include
#include
#include
class Solution {
private:
std::unordered_map buildRequirement(
const std::vector& words
) {
std::unordered_map requirement;
for (const std::string& word : words) {
++requirement[word];
}
return requirement;
}
std::vector recountEveryStart(
const std::string& s,
const std::vector& words
) {
std::vector result;
if (words.empty()) {
return result;
}
const int wordLength = static_cast(words.front().size());
const int wordCount = static_cast(words.size());
const int totalLength = wordLength * wordCount;
if (totalLength > static_cast(s.size())) {
return result;
}
const auto requirement = buildRequirement(words);
for (int start = 0;
start + totalLength <= static_cast(s.size());
++start) {
std::unordered_map 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 slidingByOffsets(
const std::string& s,
const std::vector& words
) {
std::vector result;
if (words.empty() || words.front().empty()) {
return result;
}
const int wordLength = static_cast(words.front().size());
const int wordCount = static_cast(words.size());
const int totalLength = wordLength * wordCount;
if (totalLength > static_cast(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 seen;
for (int right = offset;
right + wordLength <= static_cast(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 findSubstring(
std::string s,
std::vector& 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`` 条扫描线:
.. code-block:: text
偏移 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"]``:
.. code-block:: text
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)``。