【LeetCode】30. Substring with Concatenation of All Words（C++）_30. substring with concatenation of all words c++

地址：https://leetcode.com/problems/substring-with-concatenation-of-all-words/

题目：

You are given a string, s, and a list of words, words, that are all of the same length. Find all starting indices of substring(s) in s that is a concatenation of each word in words exactly once and without any intervening characters.
Example 1:

Input: s = “barfoothefoobarman”, words = [“foo”,“bar”]
Output: [0,9]
Explanation: Substrings starting at index 0 and 9 are “barfoor” and “foobar” respectively. The output order does not matter, returning [9,0] is fine too.

Example 2:

Input: s = “wordgoodgoodgoodbestword”, words = [“word”,“good”,“best”,“word”]
Output: []

理解：

就是寻找子串的起始位置，使得该位置开始的子串包含且仅包含一次words中的所有字符串。为了内层多次遍历，采用滑动窗口的思想，这样，外层只需要从0到words[0].length()-1就可以了，因为words[0].length()开始的在0开始的遍历中已经判断过了。

实现：

class Solution {
public:
	vector<int> findSubstring(string s, vector<string>& words) {
		vector<int> res;
		if (words.empty() || s.empty()) return res;
		unordered_map<string, int> table;
		for (string word : words)
			table[word]++;
		int n = s.length(), num = words.size(), len = words[0].length();
		int size = num*len;
		if (s.length() < size) return res;
		int beg = 0, end = 0, counter = table.size();
		//there are only len windows to judge
		unordered_map<string, int> curr(table);
		for (int i = 0; i < len; i++) {
			beg = i;
			end = i;
			curr = table;
			counter = table.size();
			while (end + len - 1 < s.length()) {
				string last = s.substr(end, len);
				if (curr.count(last)) {
					curr[last]--;
					if(curr[last]==0) counter--;
				}
				if (end + len - beg == size) {
					if (counter == 0)
						res.push_back(beg);
					string first = s.substr(beg, len);
					if (curr.count(first)) {
						curr[first]++;
						if (curr[first] > 0)
							counter++;
					}
					beg += len;
				}
				end += len;
			}
			
		}
		return res;
	}
};
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