LC 0583 [M] Delete Operation for Two Strings - ALawliet/algorithms GitHub Wiki

the number of deletions is equal to the number of places where both strings are different. So simply find the longest common subsequence(alphabets common in both in the same order) and subtract it from both the strings to find the elements that have to be deleted

### LCS
if x == y:
    T[r][c] = T[r-1][c-1] + 1
else:
    T[r][c] = max(T[r-1][c], T[r][c-1])

###
T[r][c] = T[r-1][c-1] + 1 if x == y else max(T[r-1][c], T[r][c-1])

###
Tr[c][c] = max(
    T[r-1][c-1] + (x == y), T[r-1][c],
    T[r][c-1],
)

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        def lcs():
            ROWS = len(word1)
            COLS = len(word2)

            T = [ [0]*(COLS + 1) for _ in range(ROWS + 1) ]

            for r, x in enumerate(word1,1):
                for c, y in enumerate(word2,1):
                    T[r][c] = max(
                        T[r-1][c-1] + (x == y), T[r-1][c],
                        T[r][c-1],
                    )

            return T[-1][-1] 

        return len(word1) + len(word2) - 2*lcs()