Substring with Concatenation of All Words

You are given a string, S, and a list of words, L, that are all of the same length. Find all starting indices of substring(s) in S that is a concatenation of each word in L exactly once and without any intervening characters.

For example, given:
S: "barfoothefoobarman"
L: ["foo", "bar"]

You should return the indices: [0,9].
(order does not matter).

用哈希表hashTable把L存起来，储存的是每个单词出现的个数。

在搜索时，构建一个wordCount哈希表，存储当前已经遇到的单词个数。如果遇到没有在hashTable中出现的或是遇到的同一个单词次数超出L中的限制，则break掉，进入下一次匹配。

字符串长度为n，单词长度为l，单词个数为m

复杂度o(n*m)

class Solution {
public:
    vector<int> findSubstring(string S, vector<string> &L) {
        unordered_map<string, int> hashTable;
        unordered_map<string, int> wordCount;
        vector<int > re;
        int lLen = L.size();
        if(lLen == 0) return re; 
        int wordLen = L[0].size();
        for(int i = 0; i < lLen; i++){
                hashTable[L[i]] += 1;//hashTable is initialized to 0    
        }
        for(int i = 0; i <= (int)S.size() - wordLen * lLen; i++){
            wordCount.clear();
            int wordIdx = 0;
            for(wordIdx = 0; wordIdx < lLen; wordIdx++){
                string thisWord = S.substr(i + wordIdx * wordLen, wordLen);
                if(hashTable.find(thisWord) != hashTable.end()){
                    wordCount[thisWord]++;
                    if(wordCount[thisWord] > hashTable[thisWord]){
                        break;
                    }    
                }
                else{//not found
                    break;
                }
            }
            if(wordIdx == lLen){
                re.push_back(i);
            }
        }
        return re;
    }
};

该方法比较耗时，可以还用移动窗口法。

http://www.2cto.com/kf/201406/311648.html