Edit Distance LeetCode solution in Python

1
from functools import cache
2

3

4
class Solution:
5
    def minDistance(self, word1: str, word2: str) -> int:
6
        m, n = len(word1), len(word2)
7

8
        @cache
9
        def dp(i, j):
10
            if i == 0:
11
                return j
12
            if j == 0:
13
                return i
14

15
            l1, l2 = word1[i - 1], word2[j - 1]
16
            if l1 != l2:
17
                return 1 + min(
18
                    dp(i, j - 1),  # Delete / insert j
19
                    dp(i - 1, j),  # Delete / insert i
20
                    dp(i - 1, j - 1),  # Replace i or j
21
                )
22
            return dp(i - 1, j - 1)
23

24
        return dp(m, n)