day11：415. 字符串相加、5. 最长回文子串、72. 编辑距离

输入： num1 = "11", num2 = "123"
输出： "134"

输入： num1 = "456", num2 = "77"
输出： "533"

输入： num1 = "0", num2 = "0"
输出： "0"

/**
 * @param {string} num1
 * @param {string} num2
 * @return {string}
 */
var addStrings = function(num1, num2) {
    let [len1, len2] = [num1.length, num2.length];
    let flag = 0;   // 进位标志
    let ans = '';
    for(let i = len1-1, j = len2-1; i >= 0 || j >= 0 || flag == 1; --i, --j) {
        let x, y;
        x = i >= 0? parseInt(num1[i]): 0;
        y = j >= 0? parseInt(num2[j]): 0;
        let sum = x+y+flag;
        if(sum >= 10) {
            ans += (sum%10);
            flag = 1;
        } else {
            ans += sum;
            flag = 0;
        }
    }
    return ans.split('').reverse().join('');
};

输入： s = "babad"
输出： "bab"
解释： "aba" 同样是符合题意的答案。

输入： s = "cbbd"
输出： "bb"

/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function(s) {
    let len = s.length;
    let dp = new Array(len).fill(0).map(v => (new Array(len).fill(0))); // JS初始化二维数组全为0
    let maxlen = 1;
    let ans = s[0];
    for(let i = 0; i < len; ++i) {
        dp[i][i] = 1;
        if(i > 0 && s[i-1] == s[i]) {
            dp[i-1][i] = 1;
            maxlen = 2;
            ans = s[i-1]+s[i];
        }
    }
    for(let k = 3; k <= len; ++k) {
        for(let l = 0, r = l+k-1; r < len; ++l, ++r) {
            if(s[l] == s[r] && dp[l+1][r-1] == 1) {
                dp[l][r] = 1;
                if(k > maxlen) {
                    maxlen = k;
                    ans = s.substring(l, r+1);
                }
            }
        }
    }
    return ans;
};

输入： word1 = "horse", word2 = "ros"
输出： 3
解释：
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')

输入： word1 = "intention", word2 = "execution"
输出： 5
解释：
intention -> inention (删除 't')
inention -> enention (将 'i' 替换为 'e')
enention -> exention (将 'n' 替换为 'x')
exention -> exection (将 'n' 替换为 'c')
exection -> execution (插入 'u')

/**
 * @param {string} word1
 * @param {string} word2
 * @return {number}
 */
var minDistance = function(word1, word2) {
    let [m, n] = [word1.length+1, word2.length+1];
    let dp = new Array(m).fill(0).map((v) => (new Array(n).fill(0)));
    for(let i = 0; i < m; ++i)
        dp[i][0] = i;   // word1前i个字符串变为''需要多少步
    for(let i = 0; i < n; ++i)
        dp[0][i] = i;   // word2前i个字符串变为''需要多少步
    for(let i = 1; i < m; ++i) {
        for(let j = 1; j < n; ++j) {
            if(word1[i-1] == word2[j-1])
                dp[i][j] = dp[i-1][j-1];
            else dp[i][j] = Math.min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1])+1;
        }
    }
    return dp[m-1][n-1];
};