Edit Distance Python Solution with Tests

lcpy gen -n 72   # by problem number
lcpy gen -s edit_distance   # by problem name

Input: word1 = "horse", word2 = "ros"
Output: 3
Explanation:
horse -> rorse (replace 'h' with 'r')
rorse -> rose (remove 'r')
rose -> ros (remove 'e')

Input: word1 = "intention", word2 = "execution"
Output: 5
Explanation:
intention -> inention (remove 't')
inention -> enention (replace 'i' with 'e')
enention -> exention (replace 'n' with 'x')
exention -> exection (replace 'n' with 'c')
exection -> execution (insert 'u')

class Solution:
    # Time: O(m * n)
    # Space: O(n) using a single rolling row
    def min_distance(self, word1: str, word2: str) -> int:
        m, n = len(word1), len(word2)
        # dp[j] = edit distance between word1 prefix (current row) and word2[:j]
        prev = list(range(n + 1))
        for i in range(1, m + 1):
            curr = [i] + [0] * n
            for j in range(1, n + 1):
                if word1[i - 1] == word2[j - 1]:
                    curr[j] = prev[j - 1]
                else:
                    curr[j] = 1 + min(prev[j], curr[j - 1], prev[j - 1])
            prev = curr
        return prev[n]