时间轴

2025-11-13

init

题目：

P30 串联所有单词的子串

https://leetcode.cn/problems/substring-with-concatenation-of-all-words/description/?envType=study-plan-v2&envId=top-interview-150

注意从 s 的第一个字母开始和从第二个字母开始是不同的，因此要让滑动窗口算法运行 words[0].size 次。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <vector>
#include <unordered_map>
#include <string>

using std::string;
using std::unordered_map;
using std::vector;

class Solution {
    public:
	vector<int> findSubstring(string s, vector<string> &words)
	{
		vector<int> result;
		if (s.empty() || words.empty())
			return result;

		int word_len = words[0].size();
		int num_words = words.size();
		int total_len = word_len * num_words;
		int n = s.size();

		unordered_map<string, int> word_count;
		for (auto &w : words)
			word_count[w]++;

		for (int i = 0; i < word_len; ++i) { // 0..word_len 防止漏掉
			int left = i, right = i;
			unordered_map<string, int> curr_count;

			while (right + word_len <= n) {
				string word = s.substr(right, word_len);
				right += word_len;
				if (word_count.count(word)) {
					curr_count[word]++;
					// 如果某个单词出现次数超过要求，需要收缩左边窗口
					while (curr_count[word] > word_count[word]) {
						string left_word = s.substr(left, word_len);
						curr_count[left_word]--;
						left += word_len;
					}
					// 检查窗口是否满足总长度
					if (right - left == total_len) {
						result.push_back(left);
					}
				} else {
					// 遇到不在 words 的单词，重置窗口
					curr_count.clear();
					left = right;
				}
			}
		}

		return result;
	}
};