# Time complexity of this code?

• ``````bool isScramble(string s1, string s2) {
if(s1.size() != s2.size()) return false;
if(s1 == s2) return true;
int n = s1.size();
vector<int> count(26, 0);
for(int i = 0; i < n; i++) count[s1[i]-'a']++;
for(int i = 0; i < n; i++) count[s2[i]-'a']--;
for(auto i : count){
if(i != 0) return false;
}
for(int i = 1; i < n; i++){
if((isScramble(s1.substr(0, i), s2.substr(n-i, i))&&isScramble(s1.substr(i, n-i), s2.substr(0, n-i)))||
(isScramble(s1.substr(0, i), s2.substr(0, i)) && isScramble(s1.substr(i, n-i), s2.substr(i, n-i))))
return true;
}
return false;
}
``````

find someone write this code said the time complexity is O(n^6), can someone explain why?

• Hi, for your solution, I could not understand the if condition
(isScramble(s1.substr(0, i), s2.substr(n-i, i))&&isScramble(s1.substr(i, n-i), s2.substr(0, n-i)))

This is definitely false because the length of sub-string could not be equal.
(i-(n-i))!=(i-0) in anytime and ((n-i)-i)!=((n-i)-0)in anytime either.

• @eming623 Hi, I guess you have a wrong understanding about the string's member function `substr`, the second parameter means the length of the substring, not the second position.

• I also want to ask, what is the time complexity and why?

• It's O(2^N) checkout http://n00tc0d3r.blogspot.com/2013/05/scramble-string.html

we need some math here.

for each string pair: s1 & s2, we separate each word into 2 parts and recursively check if they are scramble string,

suppose o(n) is the time complexity for strings whose size is n.
then

``````o(n) = (o(1) + o(n -1)) + (o(2) + o(n -2)) + … + (o(n - 1) + o(1)))

=> o(n) = 2 * (o(1) + … + o(n - 1))
so o(n - 1) = 2 * (o(1) + … + o(n -2))

=> o(n) - o(n - 1) = 2 * (o(n - 1))  //we minus o(n) and o(n - 1)
=> o(n) = 3 * o(n - 1) = 3^2 * o(n - 2) = ...
…
=> o(n) = 3^n that is exponential ``````

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