Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
Implementing an Established Solution solution in Clear category for String Conversion by TorinPena
#I've looked into this kind of problem before. A quick search brought up
#Levenshtein Distance, which is exactly what this problem asks for.
#The issue with copying psuedocode is avoiding off-by-one errors.
def steps_to_convert(line1, line2):
m = len(line1)
n = len(line2)
#Two work vectors created.
prev = [0]*(n+1)
curr = [0]*(n+1)
#Initialize prev, the edit distance for an empty line1.
#Range excludes the last value so +1 from psuedocode is needed.
for i in range(0, n+1):
prev[i] = i
#Calculate v1 from previous row v0.
#Range excludes the last value so -1 from psuedocode should be omitted.
for i in range(0, m):
#Calculate curr from prev.
#Edit distance of this is delete i+1 chars from s to match empty t.
curr[0] = i+1
#Fill in rest of row with formula.
for j in range(0, n):
#Initialize variable and determine if no sub_cost.
sub_cost = 1
if line1[i] == line2[j]:
sub_cost = 0
curr[j+1] = min(curr[j]+1, prev[j+1] +1, prev[j]+sub_cost)
#Copy curr to prev for next iteration.
prev = curr[:]
#After the last swap results of curr are in prev.
return prev[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!")
Sept. 24, 2017
Comments:
