A concise solution in C++


  • 0
    H

    use tow pointer to iterater, and hashmap for count

    vector<int> findSubstring(string S, vector<string> &L) {
        vector<int> res;
        int n=S.length();
        if(n==0)return res;
        
        int cnt=L.size();
        if(cnt==0)return res;
        int wlen=L[0].length();
        unordered_map<string,int> count;
        unordered_map<string,int>::iterator it;
        for(int i=0;i<cnt;i++)
        count[L[i]]++;
        
        int i=0;
        int j=0;
        while(i<n&&j<n)
        {
            unordered_map<string,int> tmpcount=count;
            int tmpcnt=cnt;
            while(i+wlen*tmpcnt<=n&&tmpcnt>0&&(it=tmpcount.find(S.substr(i,wlen)))!=tmpcount.end()&&it->second>0)
            {
                it->second--;
                tmpcnt--;
                i+=wlen;
            }
            if(tmpcnt==0)
            {
                res.push_back(j);
            }
            
            j++;
            i=j;
            if(i+wlen*cnt>n)break;
        }
        
        return res;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.