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).

vector<int> findSubstring(string S, vector<string> &L) {
    int slen = L[0].size();
    int wordsLen = slen*L.size();
    
    unordered_map<string,int>mp;
    unordered_map<string,int>cur;
    for(int i=0; i<L.size(); i++){
        mp[L[i]]++;
    }
    
    vector<int>res;
    for(int i=0; i+wordsLen <= S.size(); i++){
        cur.clear();
        bool flag = true;
        for(int j=0; j<L.size();j++){
            string temp = S.substr(i+j*slen,slen);
            if(mp.find(temp) != mp.end()){
                if(mp[temp] > cur[temp]){
                    cur[temp]++;
                }
                else{
                    flag = false;
                    break;//违背only once
                }
            }
            else{
                flag = false;
                break;
            }
        }
        
        if(flag){
            res.push_back(i);
        }
    }
    return res;
}

substring with concatenation of all words

近期文章

近期评论

标签

热门

文章归档

分类目录

功能