算法题总结-字符串编辑距离

原题
https://www.nowcoder.com/practice/3959837097c7413a961a135d7104c314?tpId=37&tqId=21275&rp=1&ru=/exam/oj/ta&qru=/exam/oj/ta&sourceUrl=%2Fexam%2Foj%2Fta%3Fdifficulty%3D3%26page%3D1%26pageSize%3D50%26search%3D%26tpId%3D37%26type%3D37&difficulty=3&judgeStatus=undefined&tags=&title=
Levenshtein 距离，又称编辑距离，指的是两个字符串之间，由一个转换成另一个所需的最少编辑操作次数。许可的编辑操作包括将一个字符替换成另一个字符，插入一个字符，删除一个字符。编辑距离的算法是首先由俄国科学家 Levenshtein 提出的，故又叫 Levenshtein Distance 。
例如：
字符串A: abcdefg
字符串B: abcdef
通过增加或是删掉字符 ”g” 的方式达到目的。这两种方案都需要一次操作。把这个操作所需要的次数定义为两个字符串的距离。
要求：
给定任意两个字符串，写出一个算法计算它们的编辑距离。
数据范围：给定的字符串长度满足 \1≤len(str)≤1000
输入示例:

abcdefg
abcdef

输出示例：

1

基本解析过程:

每种情况分以下四种情况之一[相当于动态规划表中上、左、左上三个方向的对应变化]
1、比较字符串少一个字符 改变至相同字符 可以认为是当前字符串改变 提前删除一个字符 多一个操作
2、相同比较字符串 改变至模板少一个字符串 可以认为是当前改变 之后额外增加一个字符
3、比较字符串与模板 同时增加了一个字符 但是不相同
4、比较字符串与模板 同时增加了一个字符 且相同 此时 F[i,j] = F[i-1,j-1]

核心转移方程

F[i,j] = min(F[i-1,j]+1,F[i,j-1]+1,F[i-1,j-1]+1)

源码:

import sys
count=0
string1 = ""
string2 = ""

for line in sys.stdin:
    a = line.split()
    if count==0:
        string1 = a[0]
    elif count==1:
        string2 = a[0]
    else:
        break
    count+=1
template = string1 if len(string1)>len(string2) else string2
compareStr = string1 if len(string1)<=len(string2) else string2

templateList = [item for item in template]
compareList = [item for item in compareStr]

# 动态规划表
dictionary = [[0 for j in range(len(compareList)+1)] for i in range(len(templateList)+1)]
for i in range(1,len(templateList)+1):
    dictionary[i][0] = i
    pass
for j in range(1,len(compareList)+1):
    dictionary[0][j] = j
    pass
for i in range(1,len(templateList)+1):
    for j in range(1,len(compareList)+1):
        if templateList[i-1]==compareList[j-1]:
            dictionary[i][j] = dictionary[i-1][j-1]
            pass
        else:
            dictionary[i][j] = min(dictionary[i-1][j]+1,dictionary[i][j-1]+1,dictionary[i-1][j-1]+1)
            pass
        pass
    pass
print(dictionary[-1][-1])