題目要求:
Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.
For example,
Given:
s1 = "aabcc",
s2 = "dbbca",
When s3 = "aadbbcbcac", return true.
When s3 = "aadbbbaccc", return false
簡(jiǎn)單解釋下挠唆，判斷s3是否由s1和s2交替組成，即s3前n位字符由s1的前 n-i 位字符和 s2的前 i 位字符組成嘱吗。
這是個(gè)典型的動(dòng)態(tài)規(guī)劃問(wèn)題玄组。我們保留一個(gè)二維數(shù)組 dp,
dp[i][j] 表示 s3 的前 i+j 位 字符 是否由 s1 的前 i 位 和 s2的前 j 位組成滔驾。
在已知dp[i-1][j] 和dp[i][j-1]的情況下,欲求dp[i][j],只需思考s3的第 i+j 位字符 來(lái)自 s1 的第 i 個(gè)字符 還是 s2的第 j 個(gè)字符,以及是否相等。
所以其遞推公式為:dp[i][j] = (s1[i-1] == s3[i+j-1] && dp[i-1][j]) || (s2[j-1] == s3[i+j-1] && dp[i][j-1]
- 全部代碼
public boolean isInterleave(String s1, String s2, String s3) {
if (s3.length() != s1.length() + s2.length()) return false;
boolean[][]dp = new boolean[s1.length()+1][s2.length()+1];
//初始化邊界
dp[0][0] = true;
for (int i = 1; i <=s1.length() ; i++) {
dp[i][0] = s3.charAt(i-1) == s1.charAt(i-1) ? dp[i-1][0]:false;
}
for (int i = 1; i <=s2.length() ; i++) {
dp[0][i] = s3.charAt(i-1) == s2.charAt(i-1) ? dp[0][i-1]:false;
}
for (int i = 1; i <=s1.length() ; i++) {
for (int j = 1; j <=s2.length() ; j++) {
char v3 = s3.charAt(i+j-1);
boolean v1 = v3 == s1.charAt(i-1) ? dp[i-1][j]:false;
boolean v2 = v3 == s2.charAt(j-1) ? dp[i][j-1]:false;
dp[i][j] = v1 || v2;
}
}
return dp[s1.length()][s2.length()];
}
