Description
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.
Solution
DP
唯一需要注意的就是不要越界啊。
class Solution {
public boolean isInterleave(String s1, String s2, String s3) {
if (s1 == null || s2 == null || s3 == null) {
return false;
}
int m = s1.length();
int n = s2.length();
if (m + n != s3.length()) {
return false;
}
// dp[i][j] means s1.substring(i) and s2.substring(j)
boolean[][] dp = new boolean[m + 1][n + 1];
for (int i = m; i >= 0; --i) {
for (int j = n; j >= 0; --j) {
if (i == m && j == n) {
dp[i][j] = true;
} else if (i == m) {
dp[i][j] = dp[i][j + 1] && s2.charAt(j) == s3.charAt(i + j);
} else if (j == n) {
dp[i][j] = dp[i + 1][j] && s1.charAt(i) == s3.charAt(i + j);
} else {
dp[i][j] = (dp[i + 1][j] && s1.charAt(i) == s3.charAt(i + j))
|| (dp[i][j + 1] && s2.charAt(j) == s3.charAt(i + j));
}
}
}
return dp[0][0];
}
}
