[leetcode]Scramble String

DP想老半天都想不到。。看答案也不太明解 要是面试问这个 我也就认了.. 用recursion加剪枝吧
f(n) = 2[f(1) + f(n-1)] +2[f(2) + f(n-2)] … + 2[f(n/2) + f(n/2+1)]. 易推得f(n+1) = 3(fn), 故f(n) = O(3^n)。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29

public class Solution { public boolean isScramble(String s1, String s2) { if (s1.length() != s2.length()) return false; if (s1.length() == 1) return s1.equals(s2); if (s1.equals(s2)) return true; int lookup[] = new int[26]; for (int i = 0; i < s1.length(); i++){ lookup[s1.charAt(i)-'a']++; lookup[s2.charAt(i)-'a']--; } for (int i = 0; i < 26; i++){ if (lookup[i] != 0) return false; } for (int i = 1; i < s1.length(); i++){ if (isScramble(s1.substring(0, i), s2.substring(0, i)) &&isScramble(s1.substring(i), s2.substring(i))){ return true; } if (isScramble(s1.substring(0, i), s2.substring(s2.length()-i)) &&isScramble(s1.substring(i), s2.substring(0, s2.length()-i))){ return true; } } return false; } }