# 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;
}
}``````

Last updated