# 87. Scramble String 扰乱字符串

@TOC

## # 题目描述

Given a string s1, we may represent it as a 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

To scramble the string, we may choose any non-leaf node and swap its two children.

For example, if we choose the node "gr" and swap its two children, it produces a scrambled string "rgeat".

rgeat
/    \
rg    eat
/ \    /  \
r   g  e   at
/ \
a   t

We say that "rgeat" is a scrambled string of "great".

Similarly, if we continue to swap the children of nodes "eat" and "at", it produces a scrambled string "rgtae".

rgtae
/    \
rg    tae
/ \    /  \
r   g  ta  e
/ \
t   a

We say that "rgtae" is a scrambled string of "great".

Given two strings s1 and s2 of the same length, determine if s2 is a scrambled string of s1.

Example 1:

Input: s1 = "great", s2 = "rgeat"
Output: true

Example 2:

Input: s1 = "abcde", s2 = "caebd"
Output: false

## # 解题方法

### # 递归

1. s1的[0:i]和s2[0:i]作为左子树，s1[i:N]和s2[i:N]作为右子树
2. s1的[0:i]和s2[N - i:N]作为左子树，s1的[i:N]和s2[0:N-i]作为右子树

Python代码如下：

class Solution(object):
def isScramble(self, s1, s2):
"""
:type s1: str
:type s2: str
:rtype: bool
"""
N = len(s1)
if N == 0: return True
if N == 1: return s1 == s2
if sorted(s1) != sorted(s2):
return False
for i in range(1, N):
if self.isScramble(s1[:i], s2[:i]) and self.isScramble(s1[i:], s2[i:]):
return True
elif self.isScramble(s1[:i], s2[-i:]) and self.isScramble(s1[i:], s2[:-i]):
return True
return False

C++代码如下：

class Solution {
public:
bool isScramble(string s1, string s2) {
if (s1.size() != s2.size()) return false;
const int N = s1.size();
if (N == 0) return true;
if (N == 1) return s1 == s2;
string s1copy = s1;
string s2copy = s2;
sort(s1copy.begin(), s1copy.end());
sort(s2copy.begin(), s2copy.end());
if (s1copy != s2copy) return false;
for (int i = 1; i < N; i++) {
if ((isScramble(s1.substr(0, i), s2.substr(0, i)) && isScramble(s1.substr(i), s2.substr(i))))
return true;
if ((isScramble(s1.substr(0, i), s2.substr(N - i)) && isScramble(s1.substr(i), s2.substr(0, N - i))))
return true;
}
return false;
}
};

## # 日期

2018 年 12 月 11 日 —— 双十一已经过去一个月了，真快啊。。