力扣面试150 交错字符串 二维DP
Problem: 97. 交错字符串
👨🏫 参考题解
class Solution {
public boolean isInterleave(String s1, String s2, String s3) {
int m = s1.length();
int n = s2.length();
if(s3.length() != m + n) return false;
boolean[][] dp = new boolean[m+1][n+1];
dp[0][0] = true;
for(int i = 1; i <= m && s1.charAt(i - 1) == s3.charAt(i-1); i++) // 不相符直接终止
dp[i][0] = true;
for(int i = 1; i <= n && s2.charAt(i - 1) == s3.charAt(i-1); i++) // 不相符直接终止
dp[0][i] = true;
for(int i = 1; i <= m; i++){
for(int j = 1; j <= n; j++){
dp[i][j] = (dp[i-1][j] && s3.charAt(i+j-1) == s1.charAt(i-1))
|| (dp[i][j-1] && s3.charAt(i+j-1) == s2.charAt(j-1));
}
}
return dp[m][n];
}
}