leetcode 97.
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. This is a good exercise for dp. The regularity is like below.
public static boolean isInterleave(String s1, String s2, String s3) {
if (s1.length() + s2.length() != s3.length()) {
return false;
}
boolean[][] dp = new boolean[s1.length() + 1][s2.length() + 1];
dp[0][0] = true;
for (int i = 0; i < s1.length(); i++) {
if (s1.charAt(i) != s3.charAt(i)) {
break;
}
dp[i + 1][0] = true;
}
for (int j = 0; j < s2.length(); j++) {
if (s2.charAt(j) != s3.charAt(j)) {
break;
}
dp[0][j + 1] = true;
}
for (int i = 1; i < dp.length; i++) {
for (int j = 1; j < dp[0].length; j++) {
// should pay attention that it is i + j - 1, not i + j - 2
dp[i][j] = dp[i - 1][j] && s1.charAt(i - 1) == s3.charAt(i + j - 1)
|| dp[i][j - 1] && s2.charAt(j - 1) == s3.charAt(i + j - 1);
}
}
return dp[s1.length()][s2.length()];
}
Check my code on github.