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)
有问题欢迎指出~?
|