Posted on 2013-05-22 22:25
小明 閱讀(6140)
評(píng)論(0) 編輯 收藏 所屬分類(lèi):
數(shù)據(jù)結(jié)構(gòu)和算法
分析：
這個(gè)問(wèn)題是google的面試題。由于一個(gè)字符串有很多種二叉表示法，貌似很難判斷兩個(gè)字符串是否可以做這樣的變換。
對(duì)付復(fù)雜問(wèn)題的方法是從簡(jiǎn)單的特例來(lái)思考，從而找出規(guī)律。
先考察簡(jiǎn)單情況：
字符串長(zhǎng)度為1：很明顯，兩個(gè)字符串必須完全相同才可以。
字符串長(zhǎng)度為2：當(dāng)s1="ab", s2只有"ab"或者"ba"才可以。
對(duì)于任意長(zhǎng)度的字符串，我們可以把字符串s1分為a1,b1兩個(gè)部分，s2分為a2,b2兩個(gè)部分，滿足（(a1~a2) && (b1~b2)）或者 （(a1~b2) && (a1~b2)）
如此，我們找到了解決問(wèn)題的思路。首先我們嘗試用遞歸來(lái)寫(xiě)。
解法一（遞歸）
兩個(gè)字符串的相似的必備條件是含有相同的字符集。簡(jiǎn)單的做法是把兩個(gè)字符串的字符排序后，然后比較是否相同。
加上這個(gè)檢查就可以大大的減少遞歸次數(shù)。
代碼如下：
public boolean isScramble(String s1, String s2) {
int l1 = s1.length();
int l2 = s2.length();
if(l1!=l2){
return false;
}
if(l1==0){
return true;
}
char[] c1 = s1.toCharArray();
char[] c2 = s2.toCharArray();
if(l1==1){
return c1[0]==c2[0];
}
Arrays.sort(c1);
Arrays.sort(c2);
for(int i=0;i<l1;++i){
if(c1[i]!=c2[i]){
return false;
}
}
boolean result = false;
for(int i=1;i<l1 && !result;++i){
String s11 = s1.substring(0,i);
String s12 = s1.substring(i);
String s21 = s2.substring(0,i);
String s22 = s2.substring(i);
result = isScramble(s11,s21) && isScramble(s12,s22);
if(!result){
String s31 = s2.substring(0,l1-i);
String s32 = s2.substring(l1-i);
result = isScramble(s11,s32) && isScramble(s12,s31);
}
}
return result;
}
解法二（動(dòng)態(tài)規(guī)劃）
減少重復(fù)計(jì)算的方法就是動(dòng)態(tài)規(guī)劃。動(dòng)態(tài)規(guī)劃是一種神奇的算法技術(shù)，不親自去寫(xiě)，是很難完全掌握動(dòng)態(tài)規(guī)劃的。
這里我使用了一個(gè)三維數(shù)組boolean result[len][len][len],其中第一維為子串的長(zhǎng)度，第二維為s1的起始索引，第三維為s2的起始索引。
result[k][i][j]表示s1[i...i+k]是否可以由s2[j...j+k]變化得來(lái)。
代碼如下，非常簡(jiǎn)潔優(yōu)美：
public class Solution {
public boolean isScramble(String s1, String s2) {
int len = s1.length();
if(len!=s2.length()){
return false;
}
if(len==0){
return true;
}
char[] c1 = s1.toCharArray();
char[] c2 = s2.toCharArray();
boolean[][][] result = new boolean[len][len][len];
for(int i=0;i<len;++i){
for(int j=0;j<len;++j){
result[0][i][j] = (c1[i]==c2[j]);
}
}
for(int k=2;k<=len;++k){
for(int i=len-k;i>=0;--i){
for(int j=len-k;j>=0;--j){
boolean r = false;
for(int m=1;m<k && !r;++m){
r = (result[m-1][i][j] && result[k-m-1][i+m][j+m]) || (result[m-1][i][j+k-m] && result[k-m-1][i+m][j]);
}
result[k-1][i][j] = r;
}
}
}
return result[len-1][0][0];
}
}