# How do we analyze the complexity of the solution?

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

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

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