Recursive Solution,16ms,easily understand


  • -1
    W
    class Solution {
    public:
        bool isScramble(string s1, string s2) {
            if(s1.size() != s2.size()) return false;
            if(s1 == s2) return true;
            string temp1 = s1;
            string temp2 = s2;
            sort(temp1.begin(),temp1.end());
            sort(temp2.begin(),temp2.end());
            if(temp1 != temp2) return false;//剪枝
            for(int i = 1;i < s1.size();i++){
                string s11 = s1.substr(0,i);
                string s12 = s1.substr(i);
                string s21 = s2.substr(0,i);
                string s22 = s2.substr(i);
                if(isScramble(s11,s21)&&isScramble(s12,s22)) return true;
                s21 = s2.substr(s2.size()-i);
                s22 = s2.substr(0,s2.size()-i);
                if(isScramble(s11,s21)&&isScramble(s12,s22)) return true;
             }
             return false;
        }
    };

  • 0
    M

    Hi, this solution is greater than DP solution.
    Can you help analyze the time complexity of this algorithm to us?


Log in to reply
 

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