18 lines
711 B
Python
18 lines
711 B
Python
def levenshteinDistance(str1, str2):
|
|
m = len(str1)
|
|
n = len(str2)
|
|
d = [[i] for i in range(1, m + 1)] # d matrix rows
|
|
d.insert(0, list(range(0, n + 1))) # d matrix columns
|
|
for j in range(1, n + 1):
|
|
for i in range(1, m + 1):
|
|
if str1[i - 1] == str2[j - 1]: # Python (string) is 0-based
|
|
substitutionCost = 0
|
|
else:
|
|
substitutionCost = 1
|
|
d[i].insert(j, min(d[i - 1][j] + 1,
|
|
d[i][j - 1] + 1,
|
|
d[i - 1][j - 1] + substitutionCost))
|
|
return d[-1][-1]
|
|
|
|
print(levenshteinDistance("kitten","sitting"))
|
|
print(levenshteinDistance("rosettacode","raisethysword"))
|