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}