Hard

Edit Distance

097

Return the minimum number of insertions, deletions, and replacements needed to convert word1 into word2.

EXAMPLES

Example 1

Input
{
  "word1": "horse",
  "word2": "ros"
}

Output
3

FUNCTION SHAPE

word1: stringword2: string→int

SOLUTION NOTE

Classic string DP. If characters match, no operation needed. Otherwise, try all three operations and take minimum.

Reveal reference solution +

pythonREFERENCE

def minDistance(self, word1: str, word2: str) -> int:
    @cache
    def dp(i, j):
        if i < 0: return j + 1  # Insert remaining
        if j < 0: return i + 1  # Delete remaining
        if word1[i] == word2[j]:
            return dp(i-1, j-1)  # Match, no cost
        return 1 + min(
            dp(i-1, j-1),  # Replace
            dp(i-1, j),    # Delete from word1
            dp(i, j-1)     # Insert into word1
        )

    return dp(len(word1)-1, len(word2)-1)

TimeO(m × n)

SpaceO(m × n)

Open on LeetCode ↗