题解 | #75.编辑距离(一)#

看了题解原来这道题这么简单😱

下面我就要抄题解了

$dp[i][j]dp[i][j]$表示为从$st{r}_{1}str\_1$的前$ii$位变化为$st{r}_{2}str\_2$的前$jj$位需要的次数

$str1[i]==str2[j]=>dp[i][j]=dp[i\mathrm{-}1][j\mathrm{-}1]str1[i]==str2[j]=>dp[i][j]=dp[i-1][j-1]$

$str1[i]!=str2[j]=>dp[i][j]=min(dp[i-1][j-1],dp[i][j-1],dp[i-1][j])+1;str1[i]!=str2[j]=>dp[i][j]=min(dp[i-1][j-1],\; dp[i][j-1],\; dp[i-1][j])\; +1;$

dp[i-1][j-1]对应于修改一个字符

dp[i][j-1]对应于删除一个字符

dp[i-1][j]对应于插入一个字符

function editDistance( str1 ,  str2 ) {
  
  let dp = new Array(str1.length+1);
  for(let i=0; i<dp.length; i++)
    dp[i] = new Array(str2.length+1);
  
  //初始化dp
  dp[0][0] = 0;
  for(let i=1; i<dp.length; i++)
    dp[i][0] = dp[i-1][0] + 1;
  for(let i=1; i<dp[0].length; i++)
    dp[0][i] = dp[0][i-1] + 1;
  
  for(let i=1; i<dp.length; i++){
    for(let j=1; j<dp[0].length; j++){
      if(str1[i-1] == str2[j-1])
         dp[i][j] = dp[i-1][j-1];
      else
        dp[i][j] = Math.min(dp[i-1][j-1], dp[i][j-1], dp[i-1][j]) +1;
    }
  }
  
  return dp[str1.length][str2.length];
}
module.exports = {
    editDistance : editDistance
};