题目:
给定三个字符串 s1, s2, s3, 验证 s3 是否是由 s1 和 s2 交错组成的。
输入: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
输出: true
输入: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
输出: false
那么重新理下思路:
初始值即特殊情况
实现
/**
* @param {string} s1
* @param {string} s2
* @param {string} s3
* @return {boolean}
*/
var isInterleave = function(s1, s2, s3) {
let len1 = s1.length,
len2 = s2.length,
len3 = s3.length,
dp = Array(len1+1);
if(len1+len2 !== len3) return false;
if(len1===0) return s2 === s3;
if(len2===0) return s1 === s3;
for(let i = 0;i <= len1;i++){
dp[i] = Array(len2+1)
}
dp[0][0] = true
for(let i = 0 ; i <= len1; i++){
for(let j=0; j<= len2; j++){
let p = i+j;
// 关系式中涉及i-1,j-1,避免越界区分判断
if(i > 0){
dp[i][j] = (s3[p-1] === s1[i-1] && dp[i-1][j])
|| Boolean(dp[i][j])
}
if(j > 0){
dp[i][j] = Boolean(dp[i][j])
|| (s3[p-1] === s2[j-1] && dp[i][j-1])
}
}
}
return dp[len1][len2];
};
优化空间复杂度
/**
* @param {string} s1
* @param {string} s2
* @param {string} s3
* @return {boolean}
*/
var isInterleave = function(s1, s2, s3) {
let len1 = s1.length,
len2 = s2.length,
len3 = s3.length,
dp = Array(len2);
if(len1+len2 !== len3) return false;
if(len1===0) return s2 === s3;
if(len2===0) return s1 === s3;
dp[0] = true
for(let i = 0 ; i <= len1; i++){
for(let j=0; j<= len2; j++){
let p = i+j;
// 关系式中涉及i-1,j-1,避免越界区分判断
if(i > 0){
dp[j] = (s3[p-1] === s1[i-1]) && dp[j]
}
if(j > 0){
dp[j] = Boolean(dp[j]) || (s3[p-1] === s2[j-1] && dp[j-1])
}
}
}
return dp[len2];
};