Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
First solution in Clear category for String Conversion by jcg
# https://en.wikipedia.org/wiki/Levenshtein_distance
def LevenshteinDistance(s, t):
m = len(s)
n = len(t)
d = [[0]*(n+1) for i in range(m+1)]
# source prefixes can be transformed into empty string by
# dropping all characters
for i in range(1,m+1):
d[i][0] = i
# target prefixes can be reached from empty source prefix
# by inserting every character
for j in range(1,n+1):
d[0][j] = j
for j in range(1,n+1):
for i in range(1,m+1):
if s[i-1] == t[j-1]:
substitutionCost = 0
else:
substitutionCost = 1
d[i][j] = min(d[i-1][j] + 1, # deletion
d[i][j-1] + 1, # insertion
d[i-1][j-1] + substitutionCost) # substitution
return d[m][n]
def steps_to_convert(line1, line2):
return LevenshteinDistance(line1, line2)
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. 2, 2016
