首页 > 代码库 > [leecode]Scramble String
[leecode]Scramble String
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 tTo 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 tWe 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 aWe 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.
算法思路:
分治法:其实就是暴力法= =///
代码如下:
1 public class Solution { 2 public boolean isScramble(String s1,String s2){ 3 if(s1.length() != s2.length()) return false; 4 if(s1.length() <= 1 && s1.equals(s2)) return true; 5 if(s1.length() == 2){ 6 if(s1.equals(s2) ) return true; 7 if(s1.charAt(0) == s2.charAt(1) && s1.charAt(1) == s2.charAt(0)) return true; 8 return false; 9 }10 char[] s1Array = s1.toCharArray();11 char[] s2Array = s2.toCharArray();12 Arrays.sort(s2Array);13 Arrays.sort(s1Array);14 for(int i = 0; i < s1.length(); i++){15 if(s1Array[i] != s2Array[i])16 return false;17 }18 boolean result = false;19 for(int i = 1; i < s1.length();i++){20 String s1pre = s1.substring(0,i);21 String s1suf = s1.substring(i);22 String s2pre = s2.substring(0, i);23 String s2suf = s2.substring(i);24 result = isScramble(s1pre, s2pre) && isScramble(s1suf, s2suf);25 if(!result){26 String s3pre = s2.substring(0, s1.length() - i);27 String s3suf = s2.substring(s1.length() - i);28 result = isScramble(s1pre, s3suf) && isScramble(s1suf, s3pre);29 }30 if(result) return true;31 }32 return result;33 }34 35 }
[leecode]Scramble String