转载

LeetCode编辑距离

编辑距离

题目

给定两个单词 word1word2,计算出将 word1 转换成 word2 所使用的最少操作数 。

你可以对一个单词进行如下三种操作:

  1. 插入一个字符
  2. 删除一个字符
  3. 替换一个字符

示例 1:

输入: word1 = "horse", word2 = "ros"
输出: 3
解释: 
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')

分析

? 典型的动态规划题目,算法导论的课后题也有此题。画出状态表如下

x("") r o s
x("") 0 1 2 3
h 1
o 2
r 3
s 4
e 5

f ( i , j ) f(i,j) a 1 , a 2 , . . a i a_1, a_2, ..a_i ,编辑为 b 1 , b 2 . . . b j b_1,b_2...b_j 的最小距离(a为word1, b为word2)

f ( i , j ) = m a x { f ( i ? 1 , j ? 1 ) + 1 , f ( i ? 1 , j ) + 1 , f ( i , j ? 1 ) }      a i b j f(i,j) =max\{f(i-1,j-1) + 1, f(i-1, j)+1, f(i, j-1)\} \ \ \ \ a_i \neq b_j

f ( i , j ) = m a x { f ( i ? 1 , j ? 1 ) , f ( i ? 1 , j ) + 1 , f ( i , j ? 1 ) }      a i = = b j f(i,j) =max\{f(i-1,j-1) , f(i-1, j)+1, f(i, j-1)\} \ \ \ \ a_i == b_j

f ( i ? 1 , j ? 1 ) f ( i , j ) f(i-1, j-1) \rightarrow f(i,j) 代表替换操作

f ( i ? 1 , j ) f ( i , j ) f(i-1,j) \rightarrow f(i,j) 代表删除操作

f ( i , j ? 1 ) f ( i , j ) f(i,j-1) \rightarrow f(i,j) 代表插入操作

值得注意的是 word1, word2均有可能是空字符串,所以多加了一行一列(x代表为空)

python实现代码

class Solution:
    def minDistance(self, word1, word2):
        """ :type word1: str :type word2: str :rtype: int """
        n, m = len(word1), len(word2)
        
        dp = [[-1 for i in range(m+1)] for i in range(n+1)]
        
        for i in range(0, m+1): dp[0][i] = i
        for j in range(0, n+1): dp[j][0] = j
            
            
        for i in range(0, n+1):
            for j in range(0, m+1):
                if i == 0 or j == 0: continue
                    
                #修改一个字符
                if word1[i-1] == word2[j-1]:
                    value1 = dp[i-1][j-1]
                else: value1 = dp[i-1][j-1] + 1
                
                #增加一个字符
                value2 = dp[i][j-1] + 1
                
                #减少一个字符
                value3 = dp[i-1][j] + 1
                
                dp[i][j] = min(value1, value2, value3)
        
        return dp[n][m]
正文到此结束
本文目录