Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
forward recursive solution in Speedy category for String Conversion by Sim0000
from functools import lru_cache
@lru_cache(maxsize=2**14)
def search(s1, s2, p1, p2):
"forward recursive"
n1 = len(s1[p1:])
n2 = len(s2[p2:])
if n1 == 0 or n2 == 0: return max(n1, n2)
if s1[p1] == s2[p2]: return search(s1, s2, p1 + 1, p2 + 1)
m1 = search(s1, s2, p1 + 1, p2)
m2 = search(s1, s2, p1, p2 + 1)
m3 = search(s1, s2, p1 + 1, p2 + 1)
return min(m1, m2, m3) + 1
def steps_to_convert(line1, line2):
search.cache_clear()
return search(line1, line2, 0, 0)
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!")
Oct. 5, 2016
