Skip to main content
CodeEasy v0.1

Edit Distance

Hard Subject: 2-D Dynamic Programming
Time Complexity
O(M * N)
Space Complexity
O(M * N)

Problem Description

Problem Statement

Given two strings word1 and word2, return the minimum number of operations required to convert word1 to word2. You have the following three operations permitted on a word: Insert a character, Delete a character, Replace a character.

Example 1:

  • Input: word1 = "horse", word2 = "ros"
  • Output: 3

Optimal Solution

Python

Approach: 2-D DP

dp[i][j] represents the minimum operations to convert word1[0...i-1] to word2[0...j-1]. If chars match, dp[i][j] = dp[i-1][j-1]. If they don't, we consider the minimum of Insert (dp[i][j-1]), Delete (dp[i-1][j]), and Replace (dp[i-1][j-1]), and add 1.

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        m, n = len(word1), len(word2)
        dp = [[0] * (n + 1) for _ in range(m + 1)]

        for i in range(m + 1): dp[i][0] = i
        for j in range(n + 1): dp[0][j] = j

        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if word1[i-1] == word2[j-1]:
                    dp[i][j] = dp[i-1][j-1]
                else:
                    dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])

        return dp[m][n]