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

  • 0
    class Solution {
        bool anagram(string& s1,string& s2)
            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*sum(f(k)) k=1 to n-1
            //f(n+1)=2*sum(f(k)) k=1 to 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;

Log in to reply

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