# My c++ solution and The discussion on Time complexity

• 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;
}``````

• 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.

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