072 编辑距离

code

/**
 * @param {string} word1
 * @param {string} word2
 * @return {number}
 */
var minDistance = function(word1, word2) {
    let dp = new Array(word1.length + 1).fill(0).map(
        (item) => new Array(word2.length + 1).fill(0)
    );
    console.log(dp);
    // 单词1长度 * 单词2长度 
    // 从第一个开始 两个都有长度时候 一样的 0
    // 不一样的 替换 1 
    
    for(let i = 0; i <= word1.length; i++){
        for(let j = 0; j <= word2.length; j++){
            if(j === 0){
                if(i === 0){
                    dp[i][j] = 0;
                } else {
                    dp[i][j] = dp[i - 1][j] + 1;
                }
                continue;
            }
            if(i === 0){
                dp[i][j] = dp[i][j - 1] + 1;
                continue;
            }
            
            //  acb dbb 反正最后一个是一样的，无所谓，就是保留原来的 
            // 但是反过来的情况呢，要算最小值的吧 
            // 比如说 acb dbe来评的话 可以是 ac db + 1次替换 也可以是 acb db  + 1个， ac dbe 加一个 这种 
            // horse h 只能是加是吧
            if(word1.charAt(i - 1) === word2.charAt(j - 1)){
                dp[i][j] = dp[i - 1][j - 1];
                continue;
            }
            if(i <= word1.length && j <= word2.length){
                dp[i][j] = Math.min(Math.min(dp[i - 1][j - 1], dp[i][j - 1]), dp[i - 1][j]) + 1;
                continue;
            }

            
        }
    }
    console.log(dp);
    
};

总结

1. 语言题，说真1143我是很能理解的，这个其实也差不多
2. k么，可能吧，还是和1143是一回事，偶尔写一下可能也还好