[LeetCode]Substring with Concatenation of All Words

所有words都是等长度并且unique的，所以我们不需要考虑一个string是另一个的prefix的情况。例如abcab，words=["ab", "abc"]，显然我们应该每次尽量match到最长，如果我们只match ab那么我们得不到结果。这一题的条件帮我们排除了这种可能，本质上就类似于给定一系列的char看string是否有由这些char组成的substring。我们用sliding window动态地维护左右边界即可。碰到不match的直接跳过，match的加入，如果发现当前string的数量超过words里数量了，就移动左边界直到满足条件。假设input string长度n，每个word的长度为d，我们每次遍历的时间是n / d。我们要分别以[0, d - 1]开头遍历d次，总的时间复杂度就是n / d * d = O(n)。空间复杂度O(n)，代码如下：

	class Solution {
	public:
	vector<int> findSubstring(string s, vector<string>& words) {
	if(words.empty())return {};
	int len = s.size(), step = words[0].size(), count = words.size();
	unordered_map<string, int> map;
	vector<int> res;
	for(auto word : words)++map[word];
	for(int i = 0; i < step; ++i)
	{
	int left = i, currCount = 0;
	unordered_map<string, int> currMap;
	for(int j = i; j < len; j += step)
	{
	string str = s.substr(j, step);
	if(map.find(str) != map.end())
	{
	++currCount;
	++currMap[str];
	if(currMap[str] > map[str])
	{
	while(true)
	{
	string del = s.substr(left, step);
	--currCount;
	left += step;
	--currMap[del];
	if(!currMap[del])currMap.erase(del);
	if(del == str)break;
	}
	}
	if(currCount == count)res.push_back(left);
	}
	else
	{
	left = j + step;
	currMap.clear();
	currCount = 0;
	}
	}
	}
	return res;
	}
	};

view raw Substring with Concatenation of All Words.cpp hosted with ❤ by GitHub