Medium — Dynamic Programming | String | Two Pointers

The Problem

Given two strings word1 and word2, return the minimum number of operations required to convert word1 to word2. The allowed operations are insert, delete, or replace a character.

Approach

Use dynamic programming with a 2D table where dp[i][j] represents the minimum edit distance between the first i characters of word1 and first j characters of word2. For each cell, if characters match, take the diagonal value; otherwise, take the minimum of three operations (insert, delete, replace) plus 1.

Time: O(mn) · Space: O(mn)

Code

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

        # Create a 2D table dp to store the minimum edit distance.
        dp = [[0] * (n + 1) for _ in range(m + 1)]

        # Initialize the first row and first column of dp.
        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 the characters match, no additional operation is needed.
                if word1[i - 1] == word2[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1]
                else:
                    # Choose the minimum of the three possible operations:
                    # 1. Insert a character (dp[i][j - 1] + 1)
                    # 2. Delete a character (dp[i - 1][j] + 1)
                    # 3. Replace a character (dp[i - 1][j - 1] + 1)
                    dp[i][j] = min(dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1]) + 1

        return dp[m][n]

Watch It Run

Try it yourself: Open TraceLit and step through every line.

---

Built with TraceLit — the visual algorithm tracer for LeetCode practice.

---

▲ 0 ▼ 0

Comments

Post Comment