Time complexity of this code?


  • 1
    X
    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?


  • 0
    E

    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.


  • 0
    W

    @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.


  • 0
    Y

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


  • 4
    D

    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 

Log in to reply
 

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