class Solution {
    public boolean isScramble(String s1, String s2) {
        /* DP ques 39 
        */
        //if lengths are not equal return false
        if(s1.length() != s2.length())
        return false;

        int n = s1.length();

        //making 3d dp putting s1 on row ,s2 on col and length+1 on z axis
        boolean[][][] dp = new boolean[n][n][n+1];

        //traversing the dp

        for(int len = 1 ; len <= n ; len++){

            for(int i = 0 ; i <= n-len ; i++){

                for(int j = 0 ; j <= n - len ; j++){
                    
                    // for len 1 if chars are not equal -> false else true
                    if(len == 1)
                    dp[i][j][len] = (s1.charAt(i) == s2.charAt(j));

                    else{

                        /* making cuts on strings , and looping till either all
                        cuts have been covered or we have already found true
                        */
                        for(int k = 1 ; k < len && !dp[i][j][len];k++){
                            dp[i][j][len] = 
                            
                            //left-left             right-right
                            (dp[i][j][k] && dp[i+k][j+k][len-k]) ||
                            
                            //left - right          right - left
                            (dp[i][j+len-k][k] && dp[i+k][j][len-k]);
                        }
                    }
                }
            }
        }

        

        return dp[0][0][n];
    }
    
    //recursion 1 , recursion 2 and recursion with memoization
    // public boolean isScramble1(String s1, String s2){
    //     if(s1.equals(s2))
    //     return true;

    //     for(int i = 1 ; i < s1.length() ; i++){

    //         if(isScramble1(s1.substring(0,i),s2.substring(0,i)) && isScramble1(s1.substring(i),s2.substring(i)))) ||
    //         (isScramble1(s1.substring(0,i),s2.substring(s2.length()-i)) && isScramble1(s1.substring(i),s2.substring(0,s2.length()-i))) )
    //         return true;
    //     }
    //     return false;
    // }
    // public boolean isScramble2(String s1, String s2 , int si1 ,int ei1 , int si2 , int ei2){
    //     if(s1.equals(s2))
    //     return true;

    //     for(int i = 1 ; i < s1.length() ; i++){

    //         if( (isScramble2(s1,s2,si1,si1+i,si2,si2+i) && isScramble2(s1,s2,si1+i + 1,ei1,si2+i+1,ei2)) ||
    //         (isScramble2(s1,s2,si1,si1+i,ei2-1,ei2) && isScramble2(s1,s2,si1,si1+i+1,ei1,ei2-i-1)) )
    //         return true;
    //     }
    //     return false;

    // }
    // public boolean isScramble3(String s1, String s2 ,int si1, int si2 , int len , Boolean[][][] dp){
    //     if(s1.substring(si1,si1+len).equals(s2.substring(si2,si2+len)))
    //     return true;
        
    //     if(dp[si1][si2][len] != null)
    //     return dp[si1][si2][len];

    //     for(int k = 1 ; k<len ; k++){
    //         if((isScramble3(s1,s2,si1,si2,k,dp) && isScramble3(s1,s2,si1+k,si2+k,len-k,dp)) ||
    //         (isScramble3(s1,s2,si1,si2+len-k,k,dp) && isScramble3(s1,s2,si1+k,si2,len-k,dp))){
    //             dp[si1][si2][len];
    //             return true;
    //         }
            
    //     }
        
    //     dp[si1][si2][len] = false;
    //     return false;
    // }





}