LeetCode 面试经典 150_滑动窗口_串联所有单词的子串（32_30_C++_困难）
题目描述：
给定一个字符串 s 和一个字符串数组 words。 words 中所有字符串 长度相同。
s 中的 串联子串 是指一个包含 words 中所有字符串以任意顺序排列连接起来的子串。
例如，如果 words = [“ab”,“cd”,“ef”]， 那么 “abcdef”， “abefcd”，“cdabef”， “cdefab”，“efabcd”， 和 “efcdab” 都是串联子串。 “acdbef” 不是串联子串，因为他不是任何 words 排列的连接。
返回所有串联子串在 s 中的开始索引。你可以以 任意顺序 返回答案。
输入输出样例：
示例 1：
输入：s = “barfoothefoobarman”, words = [“foo”,“bar”]
输出：[0,9]
解释：因为 words.length== 2 同时 words[i].length == 3，连接的子字符串的长度必须为 6。
子串 “barfoo” 开始位置是 0。它是 words 中以 [“bar”,“foo”] 顺序排列的连接。
子串 “foobar” 开始位置是 9。它是 words 中以 [“foo”,“bar”] 顺序排列的连接。
输出顺序无关紧要。返回 [9,0] 也是可以的。
示例 2：
输入：s = “wordgoodgoodgoodbestword”, words = [“word”,“good”,“best”,“word”]
输出：[]
解释：因为 words.length== 4 并且 words[i].length == 4，所以串联子串的长度必须为 16。
s 中没有子串长度为 16 并且等于 words 的任何顺序排列的连接。
所以我们返回一个空数组。
示例 3：
输入：s = “barfoofoobarthefoobarman”, words = [“bar”,“foo”,“the”]
输出：[6,9,12]
解释：因为 words.length== 3 并且 words[i].length == 3，所以串联子串的长度必须为 9。
子串 “foobarthe” 开始位置是 6。它是 words 中以 [“foo”,“bar”,“the”] 顺序排列的连接。
子串 “barthefoo” 开始位置是 9。它是 words 中以 [“bar”,“the”,“foo”] 顺序排列的连接。
子串 “thefoobar” 开始位置是 12。它是 words 中以 [“the”,“foo”,“bar”] 顺序排列的连接。
提示：
1 <= s.length <= 104
1 <= words.length <= 5000
1 <= words[i].length <= 30
words[i] 和 s 由小写英文字母组成
题解：
解题思路：
思路一（滑动窗口(暴力)）：
1、具体思想为，将 s 的字符串与 words 中的字符串进行匹配，每次移动一个位置，如：第一次判断"[barfoo]thefoobarman"，第二次判断"b[arfoot]hefoobarman"。因涉及到匹配问题可以很快想到使用哈希表存储 words 中的字符串。
① 首先创建一个哈希表(words_map)存储word中字符出现的次数 ，key=word[i] (string类型) value= word[i]在 word中出现的次数。
② 从左往右控制滑动窗口的大小为 words中字符的个数，创建一个哈希表(window_map)统计滑动窗口中与 word 中相同的字符串个数。
例：s = “barfoothefoobarman”, words = [“foo”,“bar”]
- words_map={“foo”:1,“bar”:1} （注意这里匹配的是words_map和window_map中
相同字符串出现的次数是否相同） - “[barfoo]thefoobarman”，统计统计窗口中匹配字符串的个数，window_map={“foo”:1,“bar”:1}==words_map（匹配）
- “b[arfoot]hefoobarman”，统计统计窗口中匹配字符串的个数，window_map={“foo”:0,“bar”:0}!=words_map（不匹配）
- …
- …
- “barfoothefoo[barman]”，统计统计窗口中匹配字符串的个数（不匹配）,window_map={“foo”:0,“bar”:1}!=words_map（不匹配）
此算法的时间复杂度会超时，因每一次移动窗口时只移动一位字符，每次需重新统计窗口中匹配字符串的个数
2、复杂度分析：
① 时间复杂度：O(ls×n×m)，其中 ls 是输入 s 的长度，n 是 words 中每个单词的长度，其中 m 是 words 的单词数。最坏情况 每移动一位字符需对 word中所有单词进行匹配。
② 空间复杂度：O(m×n)，其中 m 是 words 的单词数，n 是 words 中每个单词的长度。统计words中单词词频的消耗，和每次滑动窗口时，需要用一个哈希表保存单词频次。
思路二（滑动窗口(控制起点和滑动距离)）：
1、此方法每次移动 word 中一个字符串的长度进行匹配，跳过了重复匹配的情况。
① 创建一个哈希表(words_map)存储word中字符出现的次数 ，key=word[i] (string) value= word[i]在 word中出现的次数。
② 从左往右控制滑动窗口的大小为 words中字符的个数，创建一个哈希表(window_map)统计滑动窗口中与 word 中相同的字符串个数。
例：s = “barfoothefoobarman”, words = [“foo”,“bar”]
words_map={“foo”:1,“bar”:1}
- 起点从 i=0 下标开始
- “[bar]foothefoobarman”，window_map={“foo”:1,“bar”:0}!=words_map（匹配个数为1）(注意这里的匹配个数指的是匹配字符串出现的次数)
- “[barfoo]thefoobarman”，window_map={“foo”:1,“bar”:1}==words_map（匹配个数为2）,统计下标
- “bar[foothe]foobarman”，"the"不存在words_map中,将窗口移动到"the"的右侧，清空window_map={“foo”:0,“bar”:0}
- “barfoothe[foo]barman”，，window_map={“foo”:1,“bar”:0}!=words_map（匹配个数为1）
- …
- …
- “barfoothefoo[barman]”，window_map={“foo”:0,“bar”:1}!=words_map（匹配个数为1）
- 起点从 i=1 下标开始
- “b[arf]oothefoobarman”，"arf"不存在words_map中,将窗口移动到"arf"的右侧，清空window_map={“foo”:0,“bar”:0}
- “barf[oot]hefoobarman”，"oot"不存在words_map中,将窗口移动到"oot"的右侧，清空window_map={“foo”:0,“bar”:0}
- “barfoot[hef]oobarman”，"hef"不存在words_map中,将窗口移动到"hef"的右侧，清空window_map={“foo”:0,“bar”:0}
- …
- …
- “barfoothefoob[arm]an”，"arm"不存在words_map中,将窗口移动到"arm"的右侧，清空window_map={“foo”:0,“bar”:0}
- 起点从 i=2 下标开始
- “ba[rfo]othefoobarman”，"rfo"不存在words_map中,将窗口移动到"rfo"的右侧，清空window_map={“foo”:0,“bar”:0}
- “barfo[oth]efoobarman”，"oth"不存在words_map中,将窗口移动到"oth"的右侧，清空window_map={“foo”:0,“bar”:0}
- “barfooth[efo]obarman”，"efo"不存在words_map中,将窗口移动到"efo"的右侧，清空window_map={“foo”:0,“bar”:0}
- …
- …
- “barfoothefooba[rma]n”，"rma"不存在words_map中,将窗口移动到"rma"的右侧，清空window_map={“foo”:0,“bar”:0}
解决了方法一中字符串重复匹配的问题。
2、复杂度分析
① 时间复杂度：O(ls×n)，其中 ls 是输入 s 的长度，n 是 words 中每个单词的长度。需要做 n 次滑动窗口，每次需要遍历一次 s。
② 空间复杂度：O(m×n)，其中 m 是 words 的单词数，n 是 words 中每个单词的长度。统计words中单词词频的消耗，和每次滑动窗口时，需要用一个哈希表保存单词频次。
代码实现
代码实现（思路一（滑动窗口(暴力)））：
class Solution1 {
public:
// 主函数，寻找所有符合条件的子串
vector<int> findSubstring(string s, vector<string>& words) {
// 获取单词的长度和单词的数量
int word_len = words[0].size(); // 每个单词的长度
int word_count = words.size(); // 单词的数量
int allWords_len = word_count * word_len; // 所有单词的总长度（即匹配的子串长度）
vector<int> ans; // 用于存储匹配的起始位置
// 如果字符串的长度小于所有单词总长度，则无法匹配，直接返回空结果
if (s.size() < allWords_len) {
return ans;
}
// 创建一个哈希表，用于记录每个单词出现的频率
unordered_map<string, int> words_map;
for (const auto &word : words) {
words_map[word]++; // 统计每个单词在words中出现的次数
}
int left = 0; // 左指针，表示当前窗口的起始位置
// 从右边开始遍历字符串，每次遍历的右边界是从第一个单词后开始
for (int right = words.size() - 1; right < s.size(); right++) {
int match = 0; // 记录匹配的单词数量
unordered_map<string, int> window_map; // 当前窗口中每个单词的计数
// 遍历窗口中的每个单词，尝试匹配所有单词
for (int i = 0; i < word_count; i++) {
// 获取当前窗口的单词（每个单词的长度是word_len）
string tmp_str = s.substr(left + word_len * i, word_len);
// 如果当前单词不在 words_map 中，则跳出循环
if (!words_map.count(tmp_str)) {
break;
}
// 更新当前窗口中的单词频率
window_map[tmp_str]++;
// 如果当前窗口中的单词与原始单词频率匹配，则增加match计数
if (window_map[tmp_str] == words_map[tmp_str]) {
match++;
}
// 如果当前单词的频率超过了words_map中的频率，说明有多余的单词，跳出循环
if (window_map[tmp_str] > words_map[tmp_str]) {
match--;
break;
}
}
// 如果match等于words_map中的单词数量，说明所有单词都已匹配
if (match == words_map.size()) {
ans.push_back(left); // 将当前的起始位置添加到答案中
}
// 每次滑动窗口时，左指针右移
left++;
}
// 返回所有符合条件的起始位置
return ans;
}
};
代码实现（思路二（滑动窗口(控制起点和滑动距离)））：
class Solution2 {
public:
vector<int> findSubstring(string s, vector<string>& words) {
int word_len = words[0].size();
int word_count = words.size();
int allWords_len = word_count * word_len;
vector<int> ans;
// 如果总长度小于子串长度，直接返回
if (s.size() < allWords_len) return ans;
// 计算单词频率
unordered_map<string, int> words_map;
for (const auto &word : words) {
words_map[word]++;
}
// 滑动窗口
for (int i = 0; i < word_len; i++) { // i 是偏移量，扫描每个可能的开始位置
int left = i;
int right = i;
int match_count = 0;
unordered_map<string, int> window_map;
while (right + word_len <= s.size()) {
string word = s.substr(right, word_len);
right += word_len;
// 如果当前单词是我们要找的词
if (words_map.count(word)) {
window_map[word]++;
match_count++;
// 如果某个单词出现次数超出预期，缩小窗口
while (window_map[word] > words_map[word]) {
string left_word = s.substr(left, word_len);
window_map[left_word]--;
match_count--;
left += word_len;
}
// 如果所有单词匹配，记录结果
if (match_count == word_count) {
ans.push_back(left);
}
} else {
// 如果当前单词不在字典中，重置窗口
window_map.clear();
match_count = 0;
left = right;
}
}
}
return ans;
}
};
以思路一为例进行调试
#include<iostream>
#include<unordered_map>
#include<vector>
using namespace std;
class Solution1 {
public:
// 主函数，寻找所有符合条件的子串
vector<int> findSubstring(string s, vector<string>& words) {
// 获取单词的长度和单词的数量
int word_len = words[0].size(); // 每个单词的长度
int word_count = words.size(); // 单词的数量
int allWords_len = word_count * word_len; // 所有单词的总长度（即匹配的子串长度）
vector<int> ans; // 用于存储匹配的起始位置
// 如果字符串的长度小于所有单词总长度，则无法匹配，直接返回空结果
if (s.size() < allWords_len) {
return ans;
}
// 创建一个哈希表，用于记录每个单词出现的频率
unordered_map<string, int> words_map;
for (const auto &word : words) {
words_map[word]++; // 统计每个单词在words中出现的次数
}
int left = 0; // 左指针，表示当前窗口的起始位置
// 从右边开始遍历字符串，每次遍历的右边界是从第一个单词后开始
for (int right = words.size() - 1; right < s.size(); right++) {
int match = 0; // 记录匹配的单词数量
unordered_map<string, int> window_map; // 当前窗口中每个单词的计数
// 遍历窗口中的每个单词，尝试匹配所有单词
for (int i = 0; i < word_count; i++) {
// 获取当前窗口的单词（每个单词的长度是word_len）
string tmp_str = s.substr(left + word_len * i, word_len);
// 如果当前单词不在 words_map 中，则跳出循环
if (!words_map.count(tmp_str)) {
break;
}
// 更新当前窗口中的单词频率
window_map[tmp_str]++;
// 如果当前窗口中的单词与原始单词频率匹配，则增加match计数
if (window_map[tmp_str] == words_map[tmp_str]) {
match++;
}
// 如果当前单词的频率超过了words_map中的频率，说明有多余的单词，跳出循环
if (window_map[tmp_str] > words_map[tmp_str]) {
match--;
break;
}
}
// 如果match等于words_map中的单词数量，说明所有单词都已匹配
if (match == words_map.size()) {
ans.push_back(left); // 将当前的起始位置添加到答案中
}
// 每次滑动窗口时，左指针右移
left++;
}
// 返回所有符合条件的起始位置
return ans;
}
};
int main(int argc, char const *argv[])
{
string s="barfoothefoobarma";
vector<string> words={"foo","bar"};
Solution1 s1;
vector<int> ans= s1.findSubstring(s,words);
for (auto &i : ans){
cout<<i<<" ";
}
return 0;
}
LeetCode 面试经典 150_滑动窗口_串联所有单词的子串（32_30)原题链接
欢迎大家和我沟通交流(✿◠‿◠)