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.
递归求解,需要剪枝,不然TLE
假设字符串s1:abc与s2:def,依次比较a与d是否可以并且bc与ef是否可以,或者是a与ef是否可以并且bc与d是否可以,然后循环比较ab与de是否可以并且c与f是否可以,或者是ab与d是否可以并且c与ef是否可以,只要有一组成立则abc成立
剪枝:对字符串s1与s2,如果其中有字符不一样,则不需要进行比对了,直接return false
class Solution { public: bool isScramble(string s1, string s2) { if(s1.size()!=s2.size())return false; if(s1==s2)return true; string t1=s1,t2=s2; sort(t1.begin(),t1.end()); sort(t2.begin(),t2.end()); if(t1!=t2)return false; for(int 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(s2.size()-i))&&isScramble(s1.substr(i),s2.substr(0,s2.size()-i)))) return true; } return false; } };