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.
定义boolean 数组result[][]表示s1的前i个字符和s2的前j个字符是否能交替组成s3的前i＋j个字符。
function：result[i][j] = result[i-1][j] &&(s1[i-1] == s3[i+j-1]) || result[i][j -1] &&(s2[j-1] == s3[i+j-1])
initialize:
result[i][0] = (s1[0...i-1] == s3[0...i-1])
result[0][j] = (s2[0...i-1] == s3[0...i-1])
返回值： result[s1.length()][s2.length()]
public class Solution {
public boolean isInterleave(String s1, String s2, String s3) {
if (s1.length() + s2.length() != s3.length()) {
return false;
}
int m = s1.length();
int n = s2.length();
boolean[][] result = new boolean[m + 1][n + 1];
result[0][0] = true;
for (int i = 1; i < m + 1; i++) {
if (result[i - 1][0] && s1.charAt(i - 1) == s3.charAt(i - 1)){
result[i][0] = true;
}
}
for (int j = 1; j < n + 1; j++) {
if (result[0][j - 1] && s2.charAt(j - 1) == s3.charAt(j -1)){
result[0][j] = true;
}
}
for (int i = 1; i < m + 1; i++) {
for (int j = 1; j < n + 1; j++) {
if (result[i - 1][j] && s1.charAt(i - 1) == s3.charAt(i + j - 1) || result[i][j - 1] && s2.charAt(j -1 ) == s3.charAt(i + j - 1)){
result[i][j] = true;
}
}
}
return result[m][n];
}
}