# C++ solution.What's the time complexity?

• ``````class Solution {
public:
bool anagram(string& s1,string& s2)
{
//O(n)
vector<int> cnt(256);
for(char c:s1) cnt[c]++;
for(char c:s2) if(--cnt[c]<0) return false;
for(int n:cnt) if(n) return false;
return true;
}
bool isScramble(string s1, string s2) {
if(s1.size()!=s2.size()) return false;
if(s1==s2) return true;
int n=s1.size();
//f(n)=2*(f(1)+f(n-1)+f(2)+f(n-2)+f(3)+f(n-3)...)
//f(n)=2*sum(f(k)) k=1 to n-1
//f(n+1)=2*sum(f(k)) k=1 to n
//f(n+1)-f(n)=2*f(n)
//f(n+1)=3*f(n) f(1)=1 f(n)=3^(n-1)
for(int i=1;i<n;++i)
{
string s11=s1.substr(0,i),s12=s1.substr(i);
string s21=s2.substr(0,i),s22=s2.substr(i);
string s21p=s2.substr(n-i),s22p=s2.substr(0,n-i);
if(anagram(s11,s21) && anagram(s12,s22) && isScramble(s11,s21) && isScramble(s12,s22)) return true;
if(anagram(s11,s21p) && anagram(s12,s22p) && isScramble(s11,s21p) && isScramble(s12,s22p)) return true;
}
return false;
}
};``````

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