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.
这道题可以使用哈希表遍历的方式解决。先用一个哈希表存储所有单词出现的次数，然后遍历字符串，用一个新的哈希表存储字串中单词出现的次数。由于规定了每个单词的长度相同，所以这种方法实现起来不难。由于好久不做题，跟着别人的想法写的答案提交了好几次才通过，果然需要多加练习。
class Solution {
public:
vector<int> findSubstring(string s, vector<string>& words) {
vector<int> res;
if(s.empty() || words.empty())
return res;
unordered_map<string, int> wordCount;
for(auto item:words){
wordCount[item]++;
}
int strLen = s.size();
int wordLen = words[0].size();
int numOfWords = words.size();
int finalIndex = strLen - wordLen*words.size();
for(int i=0; i<=finalIndex; i++){
unordered_map<string, int> tempCount;
for(int j=0; j<numOfWords; j++){
string tempStr = s.substr(i+j*wordLen, wordLen);
if(wordCount.find(tempStr) != wordCount.end()){
tempCount[tempStr]++;
if(tempCount[tempStr] > wordCount[tempStr]){
break;
}
if(j == numOfWords-1)
res.push_back(i);
}
else{
break;
}
}
}
return res;
}
};
