【一天一道LeetCode】#87. Scramble String

# 一天一道LeetCode

## （一）题目

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.

## （二）解题

```class Solution {
public:
bool isScramble(string s1, string s2) {
int len1 = s1.length();
int len2 = s2.length();
if (len1 != len2) return false;//长度不一样
if (s1 == s2) return true;//子串相等

//判断两个子串包含的字符是否相同
//最开始没加这一步，导致一直超时
vector<int> count(26,0);
for(int i = 0 ; i < len1 ; i++)
{
count[s1[i]-'a']++;
count[s2[i]-'a']--;
}
for(int i = 0 ; i < 26 ; i++)
{
if(count[i]!=0) return false;
}
//递归
for (int i = 1; i < len1; i++)
{
string subs1_1 = s1.substr(0, i);
string subs1_2 = s1.substr(i);
string subs2_1 = s2.substr(0, i);
string subs2_2 = s2.substr(i);
bool is1 = (subs1_1==subs2_1?true:isScramble(subs1_1, subs2_1)) && (subs1_2==subs2_2?true:isScramble(subs1_2, subs2_2));//这里也对递归进行了优化，相等则不进行递归
subs2_1 = s2.substr(len2-i, i);
subs2_2 = s2.substr(0,len2-i);
bool is2 = (subs1_1==subs2_1?true:isScramble(subs1_1, subs2_1)) && (subs1_2==subs2_2?true:isScramble(subs1_2, subs2_2));
if (is1 || is2) return true;//两部分任一部分为Scramble String则s1和s2就为Scramble String
}
return false;
}
};```

Esri中国首席技术官王昊谈 移动GIS 与 云GIS

VMware vSphere 5.0中文资料！

java在云上的应用

RSA2012系列（5）：虚拟化安全总揽