# Simple idea using Recursion+Memoization Java

• Could anyone help me analyze running time? I thought my solution is O(n^2), please correct me if it is wrong!! Here is the code.

public boolean isScramble(String s1, String s2) {
if(s1.length()!=s2.length())
return false;
Map<String, Boolean> memo = new HashMap<String, Boolean>();
for(Character c : s1.toCharArray()){
memo.put(""+c+","+c ,true);
}
return helper(s1, s2, memo);
}

private boolean helper(String s1, String s2, Map<String, Boolean> memo){
if(memo.containsKey(s1+","+s2))
return memo.get(s1+","+s2);
if(s1.equals(s2)){
memo.put(s1+","+s2, true);
return true;
}

for(int i=1; i<s1.length(); i++){
if(helper(s1.substring(0,i), s2.substring(0,i), memo)
&& helper(s1.substring(i), s2.substring(i), memo)){
memo.put(s1+","+s2, true);
return true;
}else if(helper(s1.substring(0,i), s2.substring(s2.length()-i), memo)
&& helper(s1.substring(i), s2.substring(0,s2.length()-i), memo)){
memo.put(s1+","+s2, true);
return true;
}
}
memo.put(s1+","+s2, false);
return false;
}

The basic idea is compare substring of s1 and s2, and use HashMap to store the compared results. For example, s1 = "great", s2 = "rgtae", we divide the problems into "g" "r" and "reat" "gtae", "gr" "rg" "eat" "tae", ... then record <"g,r", false> <"gr,rg",true>...

The total number of subproblems is O(n), since we have exactly n-1 ways to split the string. The time/subproblem is also O(n), one for loop in helper function. Based on my analysis, the total time complexity is O(n^2).