Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
Wagner-Fischer algorithm solution in Clear category for String Conversion by Phil15
def steps_to_convert(line1: str, line2: str) -> int:
""" https://en.wikipedia.org/wiki/Wagner–Fischer_algorithm """
m, n = len(line1), len(line2)
d = [[i+j if not i or not j else 0 for j in range(n+1)] for i in range(m+1)]
for i, t in enumerate(line1, 1):
for j, s in enumerate(line2, 1):
d[i][j] = d[i-1][j-1] if s==t else 1 + min(d[i-1][ j ], # deletion
d[ i ][j-1], # insertion
d[i-1][j-1]) # substitution
return d[-1][-1]
Nov. 7, 2018
Comments:
