[Leetcode]-- Scramble String

有三种情况要考虑:

1. 如果两个substring相等的话，则为true
2. 如果两个substring中间某一个点，左边的substrings为scramble string， 同时右边的substrings也为scramble string，则为true
3. 如果两个substring中间某一个点，s1左边的substring和s2右边的substring为scramble string, 同时s1右边substring和s2左边的substring也为scramble string，则为true

public class Solution {
    public boolean isScramble(String s1, String s2) {
         // DFS + Pruning
         
         int len1 = s1.length(); 
         int len2 = s2.length();
         
         if(len1 != len2) return false;
         
         int[] count = new int[26];
         
         for(int i = 0; i< len1; i++){
             count[s1.charAt(i) - 'a']++;
         }
         
         for(int i = 0; i<len2; i++){
             count[s2.charAt(i) - 'a']--;
         }
         
         for(int i = 0; i < 26; i++){
             if(count[i] != 0){
                 return false;
             }
         }
         
         if(len1 == 1 && len2 == 1) return true;
         
         for(int i = 1; i< len1; i++){
             boolean result = isScramble(s1.substring(0, i), s2.substring(0, i)) 
                           && isScramble(s1.substring(i), s2.substring(i));
             
             result = result || (isScramble(s1.substring(0,i),s2.substring(len2-i)) 
                                 && isScramble(s1.substring(i), s2.substring(0,len2 - i)));
             
             if(result){
                 return result;
             }
         }
          return false;
    }
}