How do we analyze the complexity of the solution?


  • 0
    G
    class Solution {
    public:
        vector<int> findSubstring(string S, vector<string> &L) {
            vector<int> ans;
            int m = L.size();
            if(!m)
              return ans;
                     
            map<string, int> mp;
            
            for(int i=0; i<m; i++)
            {
                mp[L[i]]++;
            }
            
            int i=0;
            int n = L[0].size();  //every one has same size
            while( i + m*n -1 < S.size())
            {
               string str = S.substr(i, m*n);    
               int j=0;
               map<string, int> dict;
               bool notBreak = true;
               while(j<m)   //walk through all dictionary words
               {
                  string tmp = str.substr(j*n,n);
                  
                  if(mp.find(tmp)==mp.end())  //didnt find this word
                    break;
                  else
                  {
                      j++;
                      dict[tmp]++;
                      if(dict[tmp] > mp[tmp])  //if count of a word is more then don't store
                      {
                        notBreak = false;  
                        break;
                      }
                  }
               }
               if(j==m && notBreak)
                 ans.push_back(i);
               i++;     
            }
            return ans;
        }
    };
    

    Can we say that complexity is O(|S|*|L|) where |L| denotes the sum of size of all string in L.


  • 0
    L

    Yes. I think your algorithm is O(n * L) n is the length of string S, L is the size of L. For every sub string starts from 0 ~ n - L * length(L[0]) it will process at most L times. Consider S : aaaaaaaaaaaaaaaaaaaa and L : aa,aa. You will get the max operation time.


Log in to reply
 

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