diff between two strings

 1import functools
 2
 3
 4def 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
31lev('sat', 'sunday')