Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
Levenshtein, memoized solution in Clear category for String Conversion by DaveDiFranco
from functools import lru_cache
#Levenshtein algorithm
@lru_cache(maxsize=None)
def steps_to_convert(a, b):
if not a: return len(b)
if not b: return len(a)
return min(
steps_to_convert(a[:-1], b) + 1,
steps_to_convert(a, b[:-1]) + 1,
steps_to_convert(a[:-1], b[:-1]) + (a[-1]!=b[-1]))
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(steps_to_convert('dsfdsfgsdherhdfshsdfbgfhfhfghgfhfghfghfghgfhfgsdfgerhtrtn', 'dsdfglj;bk;oijfghfghfghgfhfghffghfghfghgro;ldbvkjdfvlfkj;fdljh;fkgjl'))
print("You are good to go!")
Oct. 7, 2016
