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…

findSubstring.cc

class Solution {
public:
    vector<int> findSubstring(string S, vector<string> &L) {
       vector<int> ret;
        if(S.empty() || L.empty() || S.size()<L.size()*L[0].size())
            return ret;
        int wordLength = L[0].size(), sumLength=L.size()*wordLength;
        //Initilize hashtable: needFound[L[i]] is no. of occurences of L[i] in L
        unordered_map<string, int> needFound; // may contain duplicates
        for(int i=0; i<L.size(); ++i) needFound[L[i]]++; 
        //Check one by one
        for(int i=0; i<=S.size()-sumLength; ++i){
            unordered_map<string, int> hasFound; // use two hash tables to record the occurence
            int j = 0;
            while(j<sumLength){
                string cur = S.substr(i+j, wordLength);
                if(needFound.find(cur)!=needFound.end() && hasFound[cur]<needFound[cur])
                    hasFound[cur]++;
                else
                    break;
                j+=wordLength;
            }
            if(j==sumLength)
                ret.push_back(i);
        }
        return ret;
    }
};