delete_operation_for_2_strings.py

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        memo = {}

        def dfs(offset1, offset2):
            if (offset1, offset2) in memo:
                return memo[(offset1, offset2)]
            if len(word1) == offset1 or len(word2) == offset2:
                return abs((len(word1)-offset1)-(len(word2)-offset2))
            if word1[offset1] == word2[offset2]:
                result = dfs(offset1 + 1, offset2 + 1,)
                memo[(offset1+1, offset2+1)] = result
                return result

            num_steps1 = 1 + dfs(offset1 + 1, offset2)            
            num_steps2 = 1 + dfs(offset1, offset2 + 1)

            result = min(num_steps1, num_steps2)
            memo[(offset1, offset2)] = result
            return result

        return dfs(0, 0)