Posted on 2013-05-10 20:47
小明 閱讀(3232)
評論(4) 編輯 收藏 所屬分類:
數據結構和算法
解法一：（遞歸）
一個簡單的想法，是遍歷s3的每個字符，這個字符必須等于s1和s2的某個字符。如果都不相等，則返回false
我們使用3個變量i,j,k分別記錄當前s1,s2,s3的字符位置。
如果s3[k] = s1[i], i向后移動一位。如果s3[k]=s2[j],j向后移動一位。
這個題目主要難在如果s1和s2的字符出現重復的時候，就有兩種情況，i,j都可以向后一位。
下面的算法在這種情況使用了遞歸，很簡單的做法。但是效率非常差，是指數復雜度的。
public class Solution {
public boolean isInterleave(String s1, String s2, String s3) {
int l1 = s1.length();
int l2 = s2.length();
int l3 = s3.length();
if(l1+l2!=l3){
return false;
}
char[] c1 = s1.toCharArray();
char[] c2 = s2.toCharArray();
char[] c3 = s3.toCharArray();
int i=0,j=0;
for(int k=0;k<l3;++k){
char c = c3[k];
boolean m1 = i<l1 && c==c1[i];
boolean m2 = j<l2 && c==c2[j];
if(!m1 && !m2){
return false;
}
else if(m1 && m2){
String news3 = s3.substring(k+1);
return isInterleave(s1.substring(i+1),s2.substring(j),news3)
|| isInterleave(s1.substring(i),s2.substring(j+1),news3);
}
else if(m1){
++i;
}
else{
++j;
}
}
return true;
}
}
解法二：（動態規劃）
為了減少重復計算，就要使用動態規劃來記錄中間結果。
這里我使用了一個二維數組result[i][j]來表示s1的前i個字符和s2的前j個字符是否能和s3的前i+j個字符匹配。
狀態轉移方程如下：
result[i,j] = (result[i-1,j] && s1[i] = s3[i+j]) || (result[i,j-1] && s2[j] = s3[i+j]);
其中0≤i≤len(s1) ,0≤j≤len(s2)
這樣算法復雜度就會下降到O(l1*l2)
public class Solution {
public boolean isInterleave(String s1, String s2, String s3) {
int l1 = s1.length();
int l2 = s2.length();
int l3 = s3.length();
if(l1+l2!=l3){
return false;
}
char[] c1 = s1.toCharArray();
char[] c2 = s2.toCharArray();
char[] c3 = s3.toCharArray();
boolean[][] result = new boolean[l1+1][l2+1];
result[0][0] = true;
for(int i=0;i<l1;++i){
if(c1[i]==c3[i]){
result[i+1][0] = true;
}
else{
break;
}
}
for(int j=0;j<l2;++j){
if(c2[j]==c3[j]){
result[0][j+1] = true;
}
else{
break;
}
}
for(int i=1;i<=l1;++i){
char ci = c1[i-1];
for(int j=1;j<=l2;++j){
char cj = c2[j-1];
char ck = c3[i+j-1];
result[i][j] = (result[i][j-1] && cj==ck) || (result[i-1][j] && ci==ck);
}
}
return result[l1][l2];
}
}