动态规划法求解编辑距离python代码（含详细注释）

本文主要是介绍动态规划法求解编辑距离python代码（含详细注释），对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

def edit_distance(string, target):
    # 字符串长度分别为m，n

    m = len(string)
    n = len(target)
    # 初始化一个矩阵长宽为m+1、n+1
    # 第一行和第一列分别表示为其中一个字符串的第一个字符转化为第二个字符串的前j（或者j）个字符所需要的增加、删除、替换的步数
    #       0   b   c   d
    #  0    0   1   2   3
    #  a    1
    #  e    2
    #  c    3
    #  d    4
    # 比如说第一行的0,1,2,3,4分别表示从空字符串''变为'','b','bc','bcd'分别需要0,1,2,3,4步
    # 对第一列同理
    # 这就相当于动态规划的初始状态

    martrix = [[i + j for j in range(n+1)] for i in range(m+1)]

    for i in range(1,m+1):
        for j in range(1,n+1):
            # 如果i，j位置的字符相同，则不需要进行替换操作
            if string[i-1] == target[j-1]:  # 对于字符串来说，其位置索引相对于状态矩阵索引需要减1
                replace_d = 0
            else:
                replace_d = 1
            # 状态矩阵当前位置数值相对于之前的三个状态有以下三种情况：
            # 1、短的那个增加一个字符变为长的。2、长的那个减少一个变为短的。3、替换（不同则需要加1，不同则加0）
            # 选择三种情况的最小值
            martrix[i][j] = min(martrix[i - 1][j - 1] + replace_d, martrix[i - 1][j]+1, martrix[i][j - 1]+1)
    return martrix[m][n]

dis = edit_distance('abc', 'bcd')
print(dis)

有问题欢迎指出~ 

这篇关于动态规划法求解编辑距离python代码（含详细注释）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！