题目:
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.
思路:
题目中的树形结构也许会成为一个思路误区,使你直接建立树形节点去解题。其实,它仅仅是阐释一个递归方法。
但是题目中依然有个线索,及left1节点中字符的个数设为n1,right1节点中字符的个数设为n2;而另一个节点的left2字符个数为n3,right2字符个数为n4
那么,n1在不等于n2的情况下,不是等于n3就是n4.
因此,在递归的比较长度的left和right的子串的时候,截取的时候需要遵循以下规则:
for(int i=1;i<len;i++){ if((isScramble(s1.substring(0,i),s2.substring(0,i)) && isScramble(s1.substring(i),s2.substring(i))) || (isScramble(s1.substring(0,i),s2.substring(len-i)) && isScramble(s1.substring(i),s2.substring(0,len-i)))){ return true; } }
而每个isScramble在判断是否相同或者可以互相转化的时候,首先判断长度是否相同;其次比较是否相等,相等直接返回true;
否则,继续判断是否所有字母个数都相同。如果对应字母个数相同,则调用上面的循环进行下一层的比较。
AC代码:
public boolean isScramble(String s1, String s2) { int len = s1.length(); if(len!=s2.length()) return false; if(s1.equals(s2)) return true; int[] bools = new int[27]; for(char a:s1.toCharArray()){ bools[a-'a']++; } for(char b:s2.toCharArray()){ bools[b-'a']--; } for(Integer aa:bools) if(aa!=0) return false; for(int i=1;i<len;i++){ if((isScramble(s1.substring(0,i),s2.substring(0,i)) && isScramble(s1.substring(i),s2.substring(i))) || (isScramble(s1.substring(0,i),s2.substring(len-i)) && isScramble(s1.substring(i),s2.substring(0,len-i)))){ return true; } } return false; }