Check if a string is a scrambled form of another string | Java Program to check if a given string is a scrambled form of another string ; map declaration for storing key value pair means for storing subproblem result ; Strings of non - equal length cant ' be scramble strings ; Empty strings are scramble strings ; Equal strings are scramble strings ; Check for the condition of anagram ; make key of type string for search in map ; checking if both string are before calculated or not if calculated means find in map then return it 's  value ; declaring flag variable to store result ; Check if S2 [ 0. . . i ] is a scrambled string of S1 [ 0. . . i ] and if S2 [ i + 1. . . n ] is a scrambled string of S1 [ i + 1. . . n ] ; Check if S2 [ 0. . . i ] is a scrambled string of S1 [ n - i ... n ] and S2 [ i + 1. . . n ] is a scramble string of S1 [ 0. . . n - i - 1 ] ; add key & flag value to map ( store for future use ) so next time no required to calculate it again ; If none of the above conditions are satisfied ; Driver Code
import java . util . * ; public class Main { static HashMap < String , Boolean > mp = new HashMap < String , Boolean > ( ) ; static boolean isScramble ( String S1 , String S2 ) { if ( S1 . length ( ) != S2 . length ( ) ) { return false ; } int n = S1 . length ( ) ; if ( n != 0 ) { return true ; } if ( S1 == S2 ) { return true ; } String copy_S1 = S1 , copy_S2 = S2 ; char [ ] t1 = copy_S1 . toCharArray ( ) ; char [ ] t2 = copy_S2 . toCharArray ( ) ; Arrays . sort ( t1 ) ; Arrays . sort ( t2 ) ; copy_S1 = new String ( t1 ) ; copy_S2 = new String ( t2 ) ; if ( ! copy_S1 . equals ( copy_S2 ) ) { return false ; } String key = ( S1 + " ▁ " + S2 ) ; if ( mp . containsKey ( key ) ) { return mp . get ( key ) ; } boolean flag = false ; for ( int i = 1 ; i < n ; i ++ ) { if ( isScramble ( S1 . substring ( 0 , i ) , S2 . substring ( 0 , i ) ) && isScramble ( S1 . substring ( i , n ) , S2 . substring ( i , n ) ) ) { flag = true ; return true ; } if ( isScramble ( S1 . substring ( 0 , i ) , S2 . substring ( n - i , n ) ) && isScramble ( S1 . substring ( i , n ) , S2 . substring ( 0 , n - i ) ) ) { flag = true ; return true ; } } mp . put ( key , flag ) ; return false ; } public static void main ( String [ ] args ) { String S1 = " coder " ; String S2 = " ocred " ; if ( isScramble ( S1 , S2 ) ) { System . out . print ( " Yes " ) ; } else { System . out . print ( " No " ) ; } } }