C++ solution, beats 99% O(s.size())


  • 0
    P
    class Solution {
    public:
        vector<int> findSubstring(string s, vector<string>& words) {
            vector<int> ans;
            if(words.empty() || words[0].empty()) return ans;
            unordered_map<string,int> cnt;   /*Here we use cnt to count the number 
    of times that a string appears in words*/
            int n = s.size(), l = words[0].size(), m = words.size();
            for(auto w:words) cnt[w]++;
            auto f = [&cnt, &ans, &s, n, l, m](int i){ /*This is a feature of C++11, 
    using Lambda function, we can capture things instead of passing so many arguments. 
    This function do: we start from an index "i", and increase the length of window 
    by "words[0].size()" every time, meanwhile counting all the possible starting 
    points that makes the window cover all the words. The complexity of this function 
    call is O(s.size()/words[0].size()).*/
                int b = i, e = i;
                unordered_map<string,int> pl;
                while(e <= n-l){
                    string tmp = s.substr(e,l);
                    e += l;
                    if(!cnt.count(tmp)){
                        b = e;
                        pl.clear();
                    }
                    else if(pl[tmp] == cnt[tmp]){
                        while(s.substr(b,l) != tmp){
                            pl[s.substr(b,l)]--;
                            b += l;
                        }
                        b += l;
                    }
                    else{
                        pl[tmp]++;
                        if(e - b == l*m){
                            ans.push_back(b);
                            pl[s.substr(b,l)]--;
                            b += l;
                        }
                    }
                }
            };
            for(int i=0;i<l;++i) f(i); /* We call that function "words[0].size()" times, 
    which can cover all the possible configurations. Then the complexity is O(s.size()).*/
            return ans;
        }
    };
    

Log in to reply
 

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