本文主要是介绍LeetCode 题解（19）: 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 ifs2 is a scrambled string of s1.
题解：
递归解法，但是无法通过时间限制。递归时那一陀计算substr的操作一定要谨慎。准备琢磨一下动态规划做法。
class Solution {
public:bool isScramble(string s1, string s2) {if(s1.length() == 1)if(s1.compare(s2) == 0)return true;bool result = false;isScrambleRecursion(s1, s2, result);return result;}bool isScrambleRecursion(string s1, string s2, bool& result){if(s1.length() == 1)if(!s1.compare(s2)){return true;}for(int div = 0; div < s1.length()-1; div++){result = (isScrambleRecursion(s1.substr(0, div+1), s2.substr(0, div+1), result) && isScrambleRecursion(s1.substr(div+1, s1.length()-div-1), s2.substr(div+1, s2.length()-div-1), result)) ||(isScrambleRecursion(s1.substr(0, div+1), s2.substr(s2.length()-1-div, div+1), result)&& isScrambleRecursion(s1.substr(div+1, s1.length()-div-1), s2.substr(0, s2.length()-div-1), result));if(result)return true;}}
};还是递归，进行了一下“剪枝”，大大减少了不必要的比较次数，16ms通过。
class Solution {
public:bool isScramble(string s1, string s2) {if(s1.length() == 1)if(s1.compare(s2) == 0)return true;bool result = false;isScrambleRecursion(s1, s2, result);return result;}bool isScrambleRecursion(string s1, string s2, bool& result){if(s1.length() == 1)if(!s1.compare(s2)){return true;}int A[26] = {0}; for(int i = 0; i < s1.length(); i++) ++A[s1[i]-'a']; for(int j = 0; j < s2.length(); j++) --A[s2[j]-'a']; for(int k = 0; k < 26; k++) if(A[k] != 0) return false;for(int div = 0; div < s1.length()-1; div++){result = (isScrambleRecursion(s1.substr(0, div+1), s2.substr(0, div+1), result) && isScrambleRecursion(s1.substr(div+1, s1.length()-div-1), s2.substr(div+1, s2.length()-div-1), result)) ||(isScrambleRecursion(s1.substr(0, div+1), s2.substr(s2.length()-1-div, div+1), result)&& isScrambleRecursion(s1.substr(div+1, s1.length()-div-1), s2.substr(0, s2.length()-div-1), result));if(result)return true;}}
};这篇关于LeetCode 题解（19）: Scramble String的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
