leetcode每日一题（2020-07-18）：97. 交错字符串

题目描述：
给定三个字符串 s1, s2, s3, 验证 s3 是否是由 s1 和 s2 交错组成的。

今日学习：
1.遇到字符串，多想想前缀和以及动规
2.滚动数组优化：只和当前以及上一状态有关的可以进行空间优化

题解：
1.我想的稍微复杂一点的dp
2.官方dp
3.优化dp

/**
 * @param {string} s1
 * @param {string} s2
 * @param {string} s3
 * @return {boolean}
 */
//动规
var isInterleave = function(s1, s2, s3) {
    let n1 = s1.length
    let n2 = s2.length
    let n3 = s3.length
    // 长度不对肯定是false
    if(n1 + n2 != n3) return false
    // dp[i][j]表示i - 1长度的s1 + j - 1长度的s2 == i + j - 2长度的s3
    const dp = new Array(n1 + 1)
    for(let i = 0; i <= n1; i++) {
        dp[i] = new Array(n2 + 1).fill(false)
    }
    // s1，s2都是空字符串的时候，因为判断过三者长度，所以true
    dp[0][0] = true
    // s1为空，判断s2有几位和s3匹配
    for(let j = 1; j <= n2; j++) {
        if(s2[j - 1] == s3[j - 1]) {
            dp[0][j] = true
        }else {
            break
        }
    }
    // s2为空，判断s1有几位和s3匹配
    for(let i = 1; i <= n1; i++) {
        if(s1[i - 1] == s3[i - 1]) {
            dp[i][0] = true
        }else {
            break
        }
    }
    // 三种情况：
    // 1.i - 2的s1加上j - 2的s2与i + j - 4的s3匹配，那么看新进来的s1[i - 1]和s2[j - 1]是否顺序组成s3[i + j - 2][i + j - 1]
    // 2.i - 1的s1加上j - 2的s2与i + j - 3的s3匹配，那么看新进来的s2[j - 1]是否与s3[i + j - 1]相等
    // 3.i - 2的s1加上j - 1的s2与i + j - 3的s3匹配，那么看新进来的s1[i - 1]是否与s3[i + j - 1]相等
    for(let i = 1; i <= n1; i++) {
        for(let j = 1; j <= n2; j++) {
            if(dp[i - 1][j - 1] == true) {
                if(s1[i - 1] == s3[i + j - 2] && s2[j - 1] == s3[i + j - 1]) {
                    dp[i][j] = true
                }
            }
            if(dp[i][j - 1] == true) {
                if(s2[j - 1] == s3[i + j - 1]) {
                    dp[i][j] = true
                }
            }
            if(dp[i - 1][j] == true) {
                if(s1[i - 1] == s3[i + j - 1]) {
                    dp[i][j] = true
                }
            }
        }
    }
    // 返回n1个s1和n2个s2是否顺序组成s3
    return dp[n1][n2]
};
//官方动规
var isInterleave = function(s1, s2, s3) {
    // 定义状态：
    // dp[i][j] = boolean 表示，s1的前[0, i)个字符，s1的前[0, j)个字符，能够凑成s3的[0, i+j)
    // 往问题规模变小了想，假设s1/s2少一个字符，照样能拼接成s3，那么再加一个也是可以拼接成s3
    // 状态转移方程：
    // dp[i][j] = (dp[i-1][j] && s1[i-1] === s3[i+j-1]) || (dp[i][j-1] && s2[j-1] === s3[i+j-1])
    // 解释：(dp[i-1][j] && s1[i-1] === s3[i+j-1])，
    // dp[i-1][j] 意思是说s1少一个，但是s3的结尾是s1凑成的，s1再多一个也可也呀
    // dp[i][j-1] 同上；
    // base case：
    // 当s1为空的时候，dp[0][j] = (dp[0][j-1] && s2[j - 1] == s3[j - 1]) ? true : false
    // 当s2为空的时候，dp[i][0] = (dp[i-1][0] && s1[i - 1] == s3[i - 1]) ? true : false
    // dp[0][0] = true，
    // 边界，需要用到空串
    let n = s1.length;
    let m = s2.length;
    if (m + n != s3.length) {
        return false;
    }
    let dp = Array.from(Array(n + 1), () => Array(m + 1).fill(false));
    for (let i = 0; i <= n; i++) {
        for (let j = 0; j <= m; j++) {
            if(i == 0 && j == 0){
                dp[i][j] = true
            }else if (i == 0) {
                // s1 为空的情况
                dp[i][j] = (dp[i][j - 1] && s2[j - 1] == s3[j - 1]) ? true : false;
            } else if (j == 0) {
                // s2 为空的情况
                dp[i][j] = (dp[i - 1][j] && s1[i - 1] == s3[i - 1]) ? true : false;
            } else {
                dp[i][j] =
                    (dp[i - 1][j] && s1[i - 1] === s3[i + j - 1]) ||
                    (dp[i][j - 1] && s2[j - 1] === s3[i + j - 1]);
            }
        }
    }
    return dp[n][m];
}
//滚动数组优化
var isInterleave = function(s1, s2, s3) {
    let n1 = s1.length;
    let n2 = s2.length;
    if (n1 + n2 != s3.length) {
        return false;
    }
    const dp = new Array(n2 + 1).fill(false)
    dp[0] = true
    for (let i = 0; i <= n1; i++) {
        for(let j = 0; j <= n2; j++) {
            let p = i + j - 1
            if(i > 0) {
                dp[j] &= (s1[i - 1] == s3[p])
            }
            if(j > 0) {
                dp[j] |= (dp[j - 1] && s2[j - 1] == s3[p])
            }
        }
    }
    return dp[n2]
}