#72

Medium

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Edit Distance

Determine the minimum number of insertions, deletions, or replacements to transform one string into another using dynamic programming.

string dynamic programming

Problem Statement

Given two strings, word1 and word2, determine the minimum number of operations required to convert word1 into word2. Allowed operations include inserting a character, deleting a character, or replacing a character.

Return the minimum total operations needed. For example, converting 'horse' to 'ros' involves replacing 'h' with 'r', then deleting 'r' and 'e', yielding 3 operations. Input strings have lengths up to 500 and contain only lowercase English letters.

Examples

Example 1

Input: word1 = "horse", word2 = "ros"

Output: 3

horse -> rorse (replace 'h' with 'r') rorse -> rose (remove 'r') rose -> ros (remove 'e')

Example 2

Input: word1 = "intention", word2 = "execution"

Output: 5

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')

Constraints

0 <= word1.length, word2.length <= 500
word1 and word2 consist of lowercase English letters.

Solution Approach

Define the DP State

Let dp[i][j] represent the minimum operations to convert the first i characters of word1 to the first j characters of word2. This state captures all previous edits and sets up the framework for state transitions.

State Transition Formula

For each dp[i][j], if word1[i-1] equals word2[j-1], then dp[i][j] = dp[i-1][j-1]; otherwise, dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]), corresponding to deletion, insertion, or replacement.

Implementation and Space Optimization

Iteratively fill the dp table from base cases: dp[0][j] = j and dp[i][0] = i. For large strings, reduce space from O(m*n) to O(min(m,n)) by storing only the previous row, maintaining correctness while saving memory.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(m n) because each subproblem dp[i][j] is computed once, iterating through all i x j combinations. Space complexity is O(m n) for the full DP table, or O(min(m,n)) if optimized to store only one previous row, which is critical for long strings.

What Interviewers Usually Probe

Asks how the DP table represents overlapping subproblems and why it's necessary.
Checks if you can optimize space for large input strings up to 500 characters.
Inquires about handling equal characters and how it affects the state transition.

Common Pitfalls or Variants

Common pitfalls

Failing to initialize base cases correctly, leading to off-by-one errors in dp[0][j] or dp[i][0].
Confusing insertion and deletion operations, which can produce incorrect minimal edits.
Attempting recursive solutions without memoization, causing exponential time complexity and timeouts.

Follow-up variants

Compute edit distance with only insertions and deletions allowed, ignoring replacements.
Find all sequences of operations that achieve the minimum edit distance.
Apply edit distance to detect approximate string matching in a text or DNA sequence.

FAQ

What is the main pattern behind the Edit Distance problem?

The main pattern is state transition dynamic programming, where each subproblem depends on previous states representing partial string conversions.

Can the space complexity be reduced for Edit Distance?

Yes, by storing only the previous DP row, space can be reduced from O(m*n) to O(min(m,n)) without affecting correctness.

How do insertions, deletions, and replacements relate in the DP formula?

They correspond to dp[i-1][j] for deletion, dp[i][j-1] for insertion, and dp[i-1][j-1] for replacement, ensuring each choice is counted correctly.

What are common mistakes in implementing Edit Distance?

Typical mistakes include off-by-one errors, confusing insertion with deletion, and using recursive approaches without memoization.

Is Edit Distance suitable for strings of length 500?

Yes, the DP solution handles up to 500 characters efficiently, especially when optimized for space using only one previous row.

terminal

Solution

Solution 1: Dynamic Programming

We define $f[i][j]$ as the minimum number of operations to convert $word1$ of length $i$ to $word2$ of length $j$. $f[i][0] = i$, $f[0][j] = j$, $i \in [1, m], j \in [0, n]$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        m, n = len(word1), len(word2)
        f = [[0] * (n + 1) for _ in range(m + 1)]
        for j in range(1, n + 1):
            f[0][j] = j
        for i, a in enumerate(word1, 1):
            f[i][0] = i
            for j, b in enumerate(word2, 1):
                if a == b:
                    f[i][j] = f[i - 1][j - 1]
                else:
                    f[i][j] = min(f[i - 1][j], f[i][j - 1], f[i - 1][j - 1]) + 1
        return f[m][n]

Continue Practicing

#87 scramble string #91 decode ways #97 interleaving string