My c++ solution and The discussion on Time complexity


  • -1
    R

    I checked lots of the questions here, and still confused about the time complexity.
    Is it O(n), or O(nK) ? n is size of the string, and K is the length of each word
    The problem is actually, will map[s.substr(i, K)] be considered always O(1), or it is related to K? (map is the hashtable)
    If the former, then O(n), otherwise, it's O(n
    K).

    vector<int> findSubstring(string S, vector<string> &L) {
       vector<int> ret;
       if (L.empty()) return ret;
       unordered_map<string,int> m;
       for (int i = 0; i < L.size(); ++i) m[L[i]]++;
       int K = L[0].size();
       for (int k = 0; k < K; ++k) {
            int i = k;  int start = i;
            while(i+K <= S.size()) {
                string s = S.substr(i,K);
                if (m.find(s) != m.end()) {
                    if (m[s] != 0) {
                        m[s]--; i += K;
                        if (i-start == L.size()*K) 
                            ret.push_back(start);
                    } else {
                            m[S.substr(start,K)]++; start += K; 
                    }
                } else { // recover the hash table
                    while(start < i) {
                        m[S.substr(start,K)]++; start += K;
                    }
                    i += K; start = i;
                }
            }
            while(start < i) {// recover the hash table
               m[S.substr(start,K)]++; start += K;
            }
       }
       return ret;
    }

  • 0
    P

    I agree with you, I do not understand there are so many people regard their own program 's complexiblity is O(n)。Lots of soltuions actually are same.


Log in to reply
 

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