[leetcode] 87. Scramble String (Hard)

时间:2022-05-29 11:39:32

题意:

判断两个字符串是否互为Scramble字符串,而互为Scramble字符串的定义:

字符串看作是父节点,从字符串某一处切开,生成的两个子串分别是父串的左右子树,再对切开生成的两个子串继续切开,直到无法再切,此时生成为一棵二叉树。对二叉树的任一子树可任意交换其左右分支,如果S1可以通过交换变成S2,则S1,S2互为Scramble字符串。

思路:

对于分割后的子串,应有IsScramble(s1[0,i] , s2[0,i]) && IsSCramble(s1[i,length] , s2[i,length])

因为分割后可以交换子串,于是也可能有IsScramble(s1[0,i] , s2[length-i,length]) 同时 IsScramble(s1[i,length] , s2[0,length-i])

注意剪枝条件:如果两串长度不同,false;如果两串所含字符种类不同,false。

Runtime: 0 ms, faster than 100.00% of C++ online submissions for Scramble String.

class Solution
{
public:
bool isScramble(string s1, string s2)
{
if (s1.length() != s2.length())
return false;
if (s1 == s2)
return true;
int check[] = {};
int i;
for (i = ; i < s1.length(); ++i)
{
++check[s1[i] - 'a'];
--check[s2[i] - 'a'];
} for (i = ; i < ; ++i)
{
if (check[i] != )
return false;
} for (i = ; i < s1.size(); i++)
{
if (
(isScramble(s1.substr(, i), s2.substr(, i)) && isScramble(s1.substr(i), s2.substr(i))) || (isScramble(s1.substr(, i), s2.substr(s1.size() - i)) && isScramble(s1.substr(i), s2.substr(, s1.size() - i))))
return true;
}
return false;
}
};