Leetcode 87. Scramble String

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
解析：
这道题定义了一种搅乱字符串，就是说假如把一个字符串当做一个二叉树的根，然后它的非空子字符串是它的子节点，然后交换某个子字符串的两个子节点，重新爬行回去形成一个新的字符串，这个新字符串和原来的字符串互为搅乱字符串。
思路：
参考：https://www.cnblogs.com/grandyang/p/4318500.html
递归处理。
简单的说，就是s1和s2是 scramble 的话，那么必然存在一个在 s1 上的长度 l1，将 s1 分成 s11 和 s12 两段，同样有 s21 和 s22，那么要么 s11 和 s21 是 scramble 的并且 s12 和 s22 是 scramble 的；要么 s11 和 s22 是 scramble 的并且 s12 和 s21 是 scramble 的。就拿题目中的例子 rgeat 和 great 来说，rgeat 可分成 rg 和 eat 两段， great 可分成 gr 和 eat 两段，rg 和 gr 是 scrambled 的， eat 和 eat 当然是 scrambled。
具体代码如下：
[cc lang=”C++”]
class Solution {
public:
bool isScramble(string s1, string s2) {
if(s1.size() != s2.size())
return false;
if(s1 == s2)
return true;
string str1 = “”;
string str2 = “”;
str1 = s1,str2 = s2;
sort(str1.begin(), str1.end());
sort(str2.begin(), str2.end());
if(str1 != str2)
return false;
for(int i=1; i < s1.size(); i++) { string s11 = s1.substr(0,i);//当前长度i将s1分为两部分 string s12 = s1.substr(i); string s21 = s2.substr(0,i);//根据当前长度i将s2分为两部分 string s22 = s2.substr(i); if(isScramble(s11,s21) && isScramble(s12, s22)) return true; s21 = s2.substr(s2.size()-i);//长度从后切分 s22 = s2.substr(0, s2.size()-i); if(isScramble(s11,s21) && isScramble(s12, s22)) return true; } return false; } }; [/cc] 运行结果：