[leetcode] 87. Scramble String (Hard)

 题意：

判断两个字符串是否互为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[26] = {0};int i;for (i = 0; i < s1.length(); ++i){++check[s1[i] - 'a'];--check[s2[i] - 'a'];}for (i = 0; i < 26; ++i){if (check[i] != 0)return false;}for (i = 1; i < s1.size(); i++){if ((isScramble(s1.substr(0, i), s2.substr(0, i)) && isScramble(s1.substr(i), s2.substr(i))) || (isScramble(s1.substr(0, i), s2.substr(s1.size() - i)) && isScramble(s1.substr(i), s2.substr(0, s1.size() - i))))return true;}return false;}
};