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.

解题思路：统计字符串数组words的字符出现次数，将对应的key-value存储在map中。从0开始截取字符串s，截取的大小为words的大小。如果在这个长度内的任何字符都能在words中查找到，并且重复的字符不大于words中重复的字符，就记录下截取字符串s时的下标。

class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
    
     
    int j;
    vector<int> posVec;
    if(s.size()==0||words.size()==0||(words.size()*words[0].size())>s.size()) return posVec;
    unordered_map<string,int> map;
    
    int wlength = words.size();
    int wSize = words[0].size();
    int subSize = wlength*wSize;
        
    //统计words中对应的单词数量   
    for(string word:words)
    {
        map[word]++;
    }
    
    for (int i = 0; i <= s.size() - subSize; i++)
    {
        //一个临时的map，用于记录可以被找到的单词
        unordered_map<string,int> tempMap;
        for (j = 0; j < wlength ;j++)
        {
            //从s中截取与words中单词长度相同的单词，如果这个单词能在words中被找到，就将它记录下来
            string subtemp = s.substr(i+j*wSize, wSize);
            if (map.find(subtemp)!= map.end())
            {
                tempMap[subtemp]++;
                //如果该单词出现的数量大于words中该单词出现的数量，就直接跳出循环  
                if(tempMap[subtemp]>map[subtemp]) break;
            }
            else
                break;

        }
        if (j==wlength )
            posVec.push_back(i);
    }
    return posVec;        
    }
};