๐ ๐ 97. ไบค้ๅญ็ฌฆไธฒ
2022ๅนด10ๆ10ๆฅ
- algorithm
๐ ๐ 97. ไบค้ๅญ็ฌฆไธฒ
้พๅบฆ: ๐ ๐
้ฎ้ขๆ่ฟฐ
่งฃๆณ
class Solution {
public boolean isInterleave(String s1, String s2, String s3) {
// ๆ่ทฏ:
// dp[i][j]
int m = s1.length();
int n = s2.length();
int total = s3.length();
if(total != m + n) {
return false;
}
if(m == 0) {
return s2.equals(s3);
}
if(n == 0) {
return s1.equals(s3);
}
// m > 0 && n > 0 && total == m + n
boolean[][] dp = new boolean[m + 1][n + 1];
dp[0][0] = true;
for(int i = 1; i <= m; i ++) {
int p = i - 1;
if(s1.charAt(p) == s3.charAt(p)) {
dp[i][0] = dp[i - 1][0];
}
}
for(int j = 1; j <= n; j ++) {
int q = j - 1;
if(s2.charAt(q) == s3.charAt(q)) {
dp[0][j] = dp[0][j - 1];
}
}
for(int i = 1; i <= m; i ++) {
for(int j = 1; j <= n; j ++) {
int p = i - 1;
int q = j - 1;
if(s1.charAt(p) == s3.charAt(p + q + 1)) {
dp[i][j] |= dp[i - 1][j];
}
if(s2.charAt(q) == s3.charAt(p + q + 1)) {
dp[i][j] |= dp[i][j - 1];
}
}
}
return dp[m][n];
}
}