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


  • 0
    K
    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;
        }
    };

Log in to reply
 

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