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.

For example, given:

s: “barfoothefoobarman”

words: [“foo”, “bar”]

You should return the indices: [0,9].

(order does not matter).

首先将word list制成一个map。

然后逐个字符循环：

• 每次取一个单词，判断在不在map中，不在的话直接可以进行下一次循环；
• 取得的单词如果存在于map中，将这个单词加入到一个新的mapNew中；在这一过程中注意更新已有单词的计数，如果计数超过map中的对应值，进行下一次循环；
• 如果取够足量的单词后依旧未触发两个中断循环的条件，那么可以认为取单词时的位置为正确位置。

解这道题目的时候脑袋瓜子抽了……

AC代码：

class Solution {
public:
	map<string, int> wordset;
	map<string, int> test;

	vector<int> findSubstring(string s, vector<string>& words) {

		vector<int> result;

		if (words.size() == 0)
		{
			return result;
		}

		int size = words[0].size();
		for (int i = 0; i < words.size(); ++i)
		{
			auto it = wordset.find(words[i]);
			if (it == wordset.end())
			{
				pair<string, int> p(words[i], 1);
				wordset.insert(p);
			}
			else
			{
				it->second++;
			}
		}

		string substr;
		int cont = words.size() * size; //每一小段的长度
		int i = 0;
		while ((i + cont) <= s.length())
		{
			int counter = 0;
			while (counter < cont)
			{
				substr.push_back(s[i]);
				if (substr.size() == size)
				{
					auto wit = wordset.find(substr);
					if (wit == wordset.end())
					{
						substr.clear();
						break;
					}
					auto it = test.find(substr);
					if (it != test.end())
					{
						it->second++;
					}
					else
					{
						pair<string, int> p(substr, 1);
						test.insert(p);
					}
					if (wordset[substr] < test[substr])
					{
						substr.clear();
						break;
					}
					substr.clear();
				}
				++counter;
				++i;
			}
			i -= counter;
			if (counter == cont)
			{
				result.push_back(i);
			}
			test.clear();
			++i;
		}

		return result;
	}
};