[DnA] dp问题（字符串编辑距离）

来源：恒创科技编辑：恒创科技编辑部

2024-01-29 06:09:59

方案：

matrix = []
x = []
y = []

def dp(row,col):
    if row < 1 or col < 1:
        return -1

    d = 0
    for m in range(1,len(y)):
        for n in range(1,len(x)):
            #如果当前节点的 行元素 和 列元素 相等,则当前单元格的值为左上角的单元格的值
            if x[n] == y[m]:
                matrix[m][n] = matrix[m-1][n-1]
            #否则在下面三个值里面去一个最小的
            else:
                first = matrix[m-1][n]+1
                second = matrix[m][n-1]+1
                third = matrix[m-1][n-1]+1
                matrix[m][n] = min(first,second,third)

def getinput(str1,str2):
    global x
    x = [ele for ele in str1]

    global y
    y = [ele for ele in str2]

    line = []

    #构建第一行
    for i,ele in enumerate(x):
        if ele == y[0]:
            tmp = 0
        else:
            tmp = 1
        if i == 0:
            line.append(tmp)
        else:
            line.append(line[i-1]+tmp)
    matrix.append(line)


    #构建第一列
    for j,ele in enumerate(y):
        line = [0 for k in range(len(x))]
        if ele == x[0]:
            tmp = 0
        else:
            tmp = 1
        if j == 0:
            line[0] = tmp
        else:
            line[0] = matrix[j-1][0]+tmp
            matrix.append(line)

str1 = input()
str2 = input()
getinput(str1,str2)
dp(1,1)
print(matrix[len(str2)-1][len(str1)-1])