Scramble String

思路
满足条件有2种情况
1. s1前i个和s2前i个是scramble string, s1后len-i个和s2后len-i个是scramble string
2. s1前i个和s2后i个是scramble string, s1后len-i个和s2前len-i个是scramble string
可以用递归来做:

 if(isScramble(s1.substring(0,i),s2.substring(0,i))&&  
         isScramble(s1.substring(i),s2.substring(i)))  
         return true;  
       if(isScramble(s1.substring(0,i),s2.substring(s2.length()-i))&&  
         isScramble(s1.substring(i),s2.substring(0,s2.length()-i)))  
         return true;  

实现:
有一个巧妙的方式来判断在2个string长度一样的时候是否字符都匹配。如下:

 int[] letters=new int[26];  
     for(int i=0;i<s1.length();i++)  
     {  
       letters[s1.charAt(i)-'a']++;  
       letters[s2.charAt(i)-'a']--;  
     }  
     for(int i=0;i<26;i++)  
     {  
       if(letters[i]!=0) return false;  
     }  

评论

此博客中的热门博文

776. Split BST

663. Equal Tree Partition

532. K-diff Pairs in an Array