87.Scramble-String.md

87. Scramble String

---

题目地址

https://www.lintcode.com/problem/scramble-string/description

https://leetcode.com/problems/scramble-string/

题目描述

Given a string s1, we may represent it as binary tree by partitioning it to two non-empty substrings recursively.

Below is one possible representation of s1 = "great":
        great
       /     \
    gr        eat
  /    \      / \
g       r    e   at
                 / \
                a   t

Approach #1

exponential complexity O(2^n)

public class Solution {
    public boolean isScramble(String s1, String s2) {
        if (s1.equals(s2)) return true; 
        
        int[] letters = new int[26];
        for (int i=0; i<s1.length(); i++) {
            letters[s1.charAt(i)-'a']++;
            letters[s2.charAt(i)-'a']--;
        }
        for (int i=0; i<26; i++) if (letters[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;
    }
}