LeetCode 30. 串联所有单词的子串算法对比分析
1. 题目链接
LeetCode 30. 串联所有单词的子串
2. 题目描述
给定一个字符串 s 和一个字符串数组 words，words 中所有单词长度相同。要求找到 s 中所有起始索引，使得从该位置开始的连续子串包含 words 中所有单词的某种排列（不限制顺序）。
示例：
输入：s = "barfoothefoobarman", words = ["foo","bar"]
输出：[0,9]（子串 "barfoo" 和 "foobar" 符合条件）。
3. 算法思路
滑动窗口法：
- 问题转化：将
words的排列匹配问题转化为固定窗口长度的滑动窗口问题。 - 哈希表统计：用
hash1记录words中单词的出现次数，hash2记录当前窗口内单词的出现次数。 - 多起点遍历：由于单词长度固定为
nwSub，需遍历nwSub种可能的起始偏移（0 ≤ i < nwSub）。 - 窗口动态调整：
- 右指针扩展：每次截取一个单词加入窗口，更新哈希表。
- 左指针收缩：当窗口内单词数量超过
nw时，移动左指针。
- 结果判断：当窗口内单词数量等于
nw且所有单词频率匹配时，记录起始索引。
暴力枚举法：
- 遍历所有子串：枚举所有长度为
nw * nwSub的子串。 - 分割统计：将子串分割为
nw个单词，统计频率是否与words一致。
4. 示例分析
输入：s = "barfoothefoobarman", words = ["foo","bar"]
-
暴力枚举法：
- 枚举所有长度为 6 的子串，例如
"barfoo","arfoot","rfooth"等。 - 对每个子串分割为
["bar","foo"]或["arf","oot"]，检查是否与words匹配。
- 枚举所有长度为 6 的子串，例如
-
滑动窗口法：
- 当
i=0时，窗口从left=0开始，截取"bar"和"foo"，count=2，记录索引 0。 - 当
i=9时，窗口从left=9开始，截取"foo"和"bar"，count=2，记录索引 9。
- 当
5. 边界条件与注意事项
- 单词长度相同：
words中所有单词长度必须一致。 - 空输入处理：若
words为空或s长度不足，直接返回空。 - 哈希表更新：需在收缩窗口时及时减少
hash2的计数，避免无效单词干扰。
6. 代码实现
class Solution
{
public:vector<int> findSubstring(string s, vector<string>& words) {vector<int> ret;int ns = s.size(), nw = words.size(), nwSub = words[0].size();if (ns < nwSub * nw) return ret;unordered_map<string, int> hash1;for (auto& word : words) hash1[word]++;for (int i = 0; i < nwSub; i++) { // 遍历所有可能的起始偏移unordered_map<string, int> hash2;int left = i, count = 0; // left为窗口左边界for (int right = i; right + nwSub <= ns; right += nwSub) {// 截取当前单词string in = s.substr(right, nwSub);hash2[in]++;// 更新有效计数：仅在当前单词属于hash1且未超过次数时增加countif (hash1.count(in) && hash2[in] <= hash1[in]) count++;// 当窗口内的单词数量超过nw时，收缩左边界while ((right - left) / nwSub + 1 > nw) {string out = s.substr(left, nwSub);if (hash1.count(out) && hash2[out] <= hash1[out]) count--;hash2[out]--;left += nwSub; // 左指针移动一个单词长度}// 若有效计数等于nw，记录起始索引if (count == nw) ret.push_back(left);}}return ret;}
};
7.暴力枚举法与滑动窗口法对比图表
| 对比维度 | 暴力枚举法 | 滑动窗口法 |
|---|---|---|
| 核心思想 | 枚举所有长度为 nw * nwSub 的子串，分割后比较单词频率。 | 维护固定窗口长度，动态调整窗口内的单词频率。 |
| 时间复杂度 | O(ns * nw * nwSub)（每个子串需分割并统计频率）。 | O(ns * nwSub)（每个单词被处理一次）。 |
| 空间复杂度 | O(nw)（存储 words 的哈希表）。 | O(nw)（存储两个哈希表）。 |
| 实现方式 | 双重循环遍历子串，内层循环分割并统计。 | 单层循环扩展右指针，动态调整左指针。 |
| 适用场景 | 小规模数据（ns ≤ 1e3, nw ≤ 10）。 | 大规模数据（ns ≤ 1e5）。 |
| 优点 | 逻辑简单，直接穷举所有可能性。 | 时间复杂度低，适用于大规模数据。 |
| 缺点 | 数据规模大时性能极差（例如 ns=1e4 时需 1e8 次操作）。 | 需处理哈希表的动态更新和边界条件。 |
