Q39 Scramble String - LeetCode 87
Tue Mar 28 2023 09:02:44 GMT+0000 (Coordinated Universal Time)
Saved by @Ayush_dabas07
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; // } }
Comments