BinarySearch 0113 Edit Distance

Problem statement

https://binarysearch.com/problems/Edit-Distance/

Solution

Equal to Leetcode 0072. Edit Distance.

Complexity

It is O(mn) for time and space.

Code

class Solution:
    def solve(self, a, b):
        @lru_cache(None)
        def dp(i, j):
            if j == -1: return i + 1
            if i == -1: return j + 1
            cost = a[i] != b[j]
            return min(dp(i-1,j) + 1, dp(i,j-1) + 1, dp(i-1,j-1) + cost)
        
        return dp(len(a) - 1, len(b) - 1)