DP recursive with memoization O(n^3)


  • 1
    W
        public boolean isScramble(String s1, String s2) {
            if(s1.length()==0 && s1.length()==0) return true; 
            if(s1.length()!=s2.length()) return false;
            int len=s1.length();
            int[][][] dp=new int[len][len][len+1];
            return isScramble(s1,s2, 0, 0, len, dp);
        }
        
        public boolean isScramble(String s1, String s2, int start1, int start2, int len, int dp[][][]) {
        //  start1 is the s1's substring starting position,
        //  start2 is the s2's substring starting position.
        //  len is the length of the substring currently considering.
            if(dp[start1][start2][len]!=0) return dp[start1][start2][len]==2?true:false;
    
            if(len==1) {
                if(s1.charAt(start1) != s2.charAt(start2)) {
                    dp[start1][start2][1]=1;
                    return false;
                } else {
                    dp[start1][start2][1]=2;
                    return true;
                }
            }
            boolean res=false;
            for(int i=1;i<len;i++) {
                res=isScramble(s1, s2, start1, start2, i, dp) && isScramble(s1, s2, start1+i, start2+i, len-i, dp);
                if(res==true) {
                    dp[start1][start2][len]=2;
                    return true;
                }
                res=isScramble(s1, s2, start1, start2+len-i, i, dp) && isScramble(s1, s2, start1+i, start2, len-i, dp);
                if(res==true) {
                    dp[start1][start2][len]=2;
                    return true;
                }
            }
            
            dp[start1][start2][len]=1;
            return false;
        }

Log in to reply
 

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