> 文档中心 > LeetCode72-编辑距离,动态规划+滚动数组

LeetCode72-编辑距离,动态规划+滚动数组


题目链接

LeetCode72


思路

编辑距离,主要关注点在于状态转移方程:
当两字符串当前字符相等时,对答案的编辑距离没有贡献,即编辑距离等于上一个状态
当两字符串当前字符不相等时,

  • dp[i][j]+1表示在word1中插入一个正确的字符
  • dp[i+1][j]+1表示在word2中插入一个正确的字符
  • dp[i][j+1]+1表示在word1中修改一个字符使之正确

当word1[i]==word2[j]时,
dp[i+1][j+1]=dp[i][j]
当word1[i]!=word2[j]时,
dp[i+1][j+1]=min{dp[i][j]+1,dp[i+1][j]+1,dp[i][j+1]+1}


注意:

  • 对于任意一个长度为0的字符串,编辑距离等于另一个字符串的长度本身。
  • 故,在动态规划过程中,dp[i][0]=i;dp[0][j]=0

代码Golang

func minDistance(word1 string, word2 string) int {    if len(word2)*len(word1)==0{return len(word1)+len(word2)}    first,second:=make([]int,len(word2)+1),make([]int,len(word2)+1)    for i:=range first{first[i]=i}    for i:=range word1{ second[0]=i+1 for j:=range word2{     b:=j+1     if word1[i]==word2[j]{  second[b]=first[b-1]     }else{  second[b]=min(first[b]+1,min(first[b-1]+1,second[b-1]+1))     } } copy(first,second)    }    return second[len(word2)]}func min(i,j int)int{if i>j{return j}return i}