Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
Wikipedia: Levenshtein distance solution in Clear category for String Conversion by suic
def steps_to_convert(w1, w2):
"""See:
https://en.wikipedia.org/wiki/Levenshtein_distance
Iterative with full matrix
"""
m, n = map(len, (w1, w2))
distances = [
[0 for _ in range(n+1)]
for _ in range(m+1)
]
for i in range(1, m+1):
distances[i][0] = i
for j in range(1, n+1):
distances[0][j] = j
for j in range(1, n+1):
for i in range(1, m+1):
subst_cost = w1[i-1] != w2[j-1]
distances[i][j] = min(
distances[i-1][j] + 1,
distances[i][j-1] + 1,
distances[i-1][j-1] + subst_cost
)
return distances[m][n]
Oct. 5, 2016
