网站导航
> 技术文档 > LeetCode 面试经典 150_滑动窗口_串联所有单词的子串（32_30_C++_困难）(滑动窗口：控制起点和滑动距离)

LeetCode 面试经典 150_滑动窗口_串联所有单词的子串（32_30_C++_困难）(滑动窗口：控制起点和滑动距离)

网友: 技术文档 2025-09-03 05:38:53

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#include#includeusing 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)原题链接
欢迎大家和我沟通交流(✿◠‿◠)

网络标签：

相关问题