30. Substring with Concatenation

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;
    }
};