[leetcode] 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).

Algorithm:

O(MN) time complexity. M = length(S), N = length(L)*wordlen

1. setup NeedToFind and HasFound map.

2.check each char in S as start and length of N. Use another pointer in string [begin, begin+N] to check

   if words are in L.

This question is easy as you only need to maintain 2 hastable.  but remember to reset HasFound each time. And begin has to go through all the chars in S.

 At first the my code is TIME LIMIT EXCEED, but when I made the map insert without checking if it is in the map, but directly use a[xxx]++ it get passed.

So the map<string, int> seems firstly set as all zero?? 

My code:

vector findSubstring(string S, vector &L) {
        vector ret;
        if(L.size() == 0 || S.size() == 0) return ret;
        int wordlen = L[0].length();
        int alllen = wordlen*L.size();
        map NeedToFind;

        for(int i = 0; i < L.size(); i++){
                NeedToFind[L[i]]++;
        }
        int begin = 0;
        while(begin < S.length()-alllen+1){
            map HasFound;
            int j;
            for(j = begin; j < begin+alllen-wordlen+1; j = j+wordlen){
                string cur = S.substr(j, wordlen);
                if(NeedToFind.count(cur) == 0){
                    break;
                } else{
                    HasFound[cur]++;
                    if(HasFound[cur] > NeedToFind[cur]){
                       break;
                    }  
                }
            }
            j = j - wordlen;
            if(j == begin+alllen-wordlen){
                ret.push_back(begin);
                begin++;
            }else{
                begin++;
            }
        }
    }