Please help with my code


  • 0
    Y

    Below is my DP solution, I failed on test:

    Input:	  "aa", "ab"
    Output:       true
    Expected:   false
    

    I tested my solution on my local (C++ 4.2.1, Apple LLVM version 6.0) but didn't find any problem... Please help, thanks in advance!

    Below is my code in C++:

        //DP
        //f[i][j][k]: if s1[i..k] and s2[j..k] are scramble strings of each other
        //init: f[i][j][1] is true if s1[i]==s[j], false otherwise
        //goal: f[0][0][len+1]
        //iteration: f[i][j][k] = f[i][j][k] || (f[i][j][p] && f[i+p][j+p][k-p]) || (f[i][j+k-p][p] && f[i+p][j][p])
        bool isScramble(string s1, string s2) {
            if(s1.size() != s2.size()){
                return false;
            }
            if(s1 == s2){
                return true;
            }
            int len = s1.size();
            bool f[len][len][len+1];
            //init
            for(int i=0; i<len; i++){
                for(int j=0; j<len; j++){
                    f[i][j][1] = (s1[i] == s2[j]);
                }
            }
            //iteration
            for(int k=2; k<=len; k++){   //current length
                for(int i=0; i<=len-k; i++){
                    for(int j=0; j<=len-k; j++){
                        for(int p=1; p<k; p++){ //split position
                            f[i][j][k] |= (f[i][j][p] && f[i+p][j+p][k-p]) || (f[i][j+k-p][p] && f[i+p][j][p]);
                        }
                    }
                }
            }
            return f[0][0][len];
        }

Log in to reply
 

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