Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
wikipedia is my friend... solution in Clear category for String Conversion by maybe
def steps_to_convert(line1, line2):
"""Levenshtein distance,
algo taken from wikipedia, translated to python, comments are original
"""
s,t,m,n=line1,line2,len(line1),len(line2)
# create two work vectors of integer distances
v0,v1 = [0]*(n+1),[0]*(n+1)
# initialize v0 (the previous row of distances)
# this row is A[0][i]: edit distance for an empty s
# the distance is just the number of characters to delete from t
for i in range(n+1):
v0[i] = i
for i in range(m):
# calculate v1 (current row distances) from the previous row v0
# first element of v1 is A[i+1][0]
# edit distance is delete (i+1) chars from s to match empty t
v1[0] = i + 1
# use formula to fill in the rest of the row
for j in range(n):
# calculating costs for A[i+1][j+1]
deletionCost = v0[j + 1] + 1
insertionCost = v1[j] + 1
if s[i] == t[j]:
substitutionCost = v0[j]
else:
substitutionCost = v0[j] + 1;
v1[j + 1] = min(deletionCost, insertionCost, substitutionCost)
# copy v1 (current row) to v0 (previous row) for next iteration
# since data in v1 is always invalidated, a swap without copy could be more efficient
v0,v1 = v1,v0
# after the last swap, the results of v1 are now in v0
return v0[n]
if __name__ == "__main__":
#These "asserts" using only for self-checking and not necessary for auto-testing
assert steps_to_convert('line1', 'line1') == 0, "eq"
assert steps_to_convert('line1', 'line2') == 1, "2"
assert steps_to_convert('line', 'line2') == 1, "none to 2"
assert steps_to_convert('ine', 'line2') == 2, "need two more"
assert steps_to_convert('line1', '1enil') == 4, "everything is opposite"
assert steps_to_convert('', '') == 0, "two empty"
assert steps_to_convert('l', '') == 1, "one side"
assert steps_to_convert('', 'l') == 1, "another side"
print("You are good to go!")
Dec. 29, 2019
Comments:
