share my 97.26% beats cpp solution,O(n) time


  • 0
    Z
    class Solution {
    public:
        vector<int> findSubstring(string s, vector<string>& words) {
            vector<int> ret;
            if(words.empty())return ret;
            int k=words[0].size(),start=0;
            unordered_map<string,int> dict;
            for(auto s:words)dict[s]++;
            while(start<k){
                unordered_map<string,int> vis;
                int cnts=words.size(),i=start;
                while(i<s.size()){
                    string t=s.substr(i,k);
                    if(!dict.count(t)){
                        vis.clear();
                        cnts=words.size();
                    }
                    else if(vis[t]==dict[t]){
                        for(int j=i-(words.size()-cnts)*k;s.substr(j,k)!=t;j+=k){
                            vis[s.substr(j,k)]--;
                            cnts++;
                        }
                    }
                    else {
                        vis[t]++;
                        cnts--;
                        if(cnts==0){
                            ret.push_back(i-(words.size()-1)*k);
                            vis[s.substr(i-(words.size()-1)*k,k)]--;
                            cnts=1;
                        }
                    }
                    i+=k;
                }
                start++;
            }
            return ret;
        }
    };
    

Log in to reply
 

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