https://www.nowcoder.com/practice/3959837097c7413a961a135d7104c314

描述

Levenshtein 距離，又稱編輯距離，指的是兩個(gè)字符串之間，由一個(gè)轉(zhuǎn)換成另一個(gè)所需的最少編輯操作次數(shù)。許可的編輯操作包括將一個(gè)字符替換成另一個(gè)字符，插入一個(gè)字符，刪除一個(gè)字符。編輯距離的算法是首先由俄國(guó)科學(xué)家Levenshtein提出的，故又叫Levenshtein Distance。
例如：
字符串A:abcdefg
字符串B: abcdef

通過(guò)增加或是刪掉字符”g”的方式達(dá)到目的。這兩種方案都需要一次操作。把這個(gè)操作所需要的次數(shù)定義為兩個(gè)字符串的距離。
要求：
給定任意兩個(gè)字符串，寫(xiě)出一個(gè)算法計(jì)算它們的編輯距離。
本題含有多組輸入數(shù)據(jù)。

輸入描述：

每組用例一共2行，為輸入的兩個(gè)字符串

輸出描述：

每組用例輸出一行，代表字符串的距離

示例1

輸入：
abcdefg
abcdef
輸出：
1

js實(shí)現(xiàn)

參考：

• 【動(dòng)態(tài)規(guī)劃終極絕殺！ LeetCode：72.編輯距離-嗶哩嗶哩】 https://b23.tv/tuCxlgX
• http://www.itdecent.cn/p/d1d544641d47

const rl = require("readline").createInterface({ input: process.stdin });
let input_data=[]
rl.on('line',function(input){
    input_data.push(input)
    if(input_data.length===2){
        let [s1,s2]=input_data
        let dp=new Array(s1.length+1)
        for(let i=0;i<=s1.length;i++){
            dp[i]=new Array(s2.length+1)
            for(let j=0;j<=s2.length;j++){
                if(i===0){
                    dp[i][j]=j
                }else if(j===0){
                    dp[i][j]=i
                }else{
                    if(s1[i-1]===s2[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
                    }
                }
            }
        }
        console.log(dp[s1.length][s2.length])
    }
   
})