diff between two strings

🏠

https://www.pramp.com/question/5j2xWAx1qPtlZGLnG2O0

 1 import functools
 2 
 3 
 4 def lev(A, B):
 5     @functools.lru_cache(None)
 6     def dp(ai, bi):
 7         if ai < 0:
 8             return bi + 1
 9         elif bi < 0:
10             return ai + 1
11         if A[ai] == B[bi]:
12             return dp(ai - 1, bi - 1)
13         mod = dp(ai - 1, bi - 1)
14         add = dp(ai, bi - 1)
15         rem = dp(ai - 1, bi)
16         return 1 + min(mod, add, rem)
17 
18     i, j = 0, 0
19     while i < len(A) and j < len(B):
20         if A[i] == B[j]:
21             print(A[i])
22             i, j = i + 1, j + 1
23         else:
24             if dp(i+1, j) <= dp(i, j+1):
25                 print(f"-{A[i]}")
26                 i += 1
27             else:
28                 print(f"+{B[j]}")
29                 j += 1
30 
31 lev('sat', 'sunday')

See also:

levenshtein distance