HWH

Concentrate on computer science,academic research

动态规划之编辑距离(python)

问题描述

        给定两个字符串A和B,要用最少的操作将字符串A转换成字符串B。其中字符串操作包括:删除一个字符、插入一个字符、修改一个字符。

问题分析

        这是一个典型的动态规划问题,称为字符串的编辑距离。动态规划的思路是为了求解当前的问题的最优解,使用子问题的最优解,然后综合处理,最终得到原问题的最优解。那么我们要求出A转化为B的最少操作数,就把两个字符串一步步拆解开来,求出每一步的最少操作数,得到最优解。

   我们需要考虑以下情况:

(1)dp[i][j]表示将字符串A[0: i-1]转变为B[0: j-1]的最小步骤数。

(2)边界情况:
         当 i = 0,即 A 串为空时,那么转变为 B 串就是不断添加字符,dp[0][j] = j。
         当 j = 0,即 B 串为空时, 那么转变为 B 串就是不断删除字符,dp[i][0] = i。

(3)计算最小步数:

        我们构造len(A) x len(B)的矩阵代表步数,举例来说,用(1,1)表示A的第一个元素转化为B的第一个元素(二者不同),可以进行三种操作:

        a. 从(1,0)到(1,1),意义就是将A的第一个元素先删除,然后再插入B的第一个元素,也就是在(1,0)的基础上再加了一步插入操作,所以这个操作数为1+1=2;

        b. 从(0,1)到(1,1),意义就是先插入B的第一个元素,再删除A的第一个元素,也就是在(0,1)的基础上再加了一步删除操作,所以这个操作数为1+1=2;

        c. 从(0,0)到(1,1),则是当两个字符串前面都已经完全相同时,做的替换操作,所以这个操作数为0+1=1。在三者中取最小值,即为坐标(1,1)的值,为1。

最后矩阵右下角的数即为所求的最小步数。

代码示例

class Dp:
def minDistance(self, a, b):
m, n = len(a), len(b)
if m == 0:return n
if n == 0:return m
dp = [[0]*(n+1) for _ in range(m+1)] # 初始化dp和边界
for i in range(1, m+1): dp[i][0] = i #第一列
for j in range(1, n+1): dp[0][j] = j #第一行
for i in range(1, m+1):
for j in range(1, n+1):
if a[i - 1] == b[j - 1]:
dp[i][j] = dp[i - 1][j - 1]
else:
dp[i][j] = min(dp[i - 1][j - 1] + 1, min(dp[i][j - 1] + 1, dp[i - 1][j] + 1))
return dp[m][n]


if __name__ == '__main__':
dp = Dp()
a, b = 'houwenhan', 'houbiao'
print(dp.minDistance(a, b)) #运行结果为5

发表评论

电子邮件地址不会被公开。 必填项已用*标注