How do you solve Edit Distance?

Use a top-down recursive DP with memoization. The dp(i, j) function returns the minimum operations to convert word1[0..i] to word2[0..j]. If characters match, recurse on dp(i-1, j-1). Otherwise, compute the minimum among insert (dp(i, j-1)), delete (dp(i-1, j)), and replace (dp(i-1, j-1)) plus one operation. Memoize results to achieve O(m*n) time complexity, where m and n are the lengths of the input strings.

Edit Distance

Q: What is the time complexity of Edit Distance?

O(m * n). Each state (i, j) representing prefixes of word1 and word2 is computed once and stored in memo. There are m * n such states, and each computation does O(1) work.

Q: What pattern does Edit Distance use?

The Pattern: Dynamic Programming (Top-Down Memoization for Sequence Alignment) The Heuristic: When a problem asks for minimum operations to transform one sequence into another with insert/delete/replace, model it as a state machine over indices and use memoized recursion to avoid recomputation of overlapping subproblems.

Hard Dynamic Programming

Problem

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

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

Example

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

Output: 3

Transform "horse" to "ros" with minimum operations: 1. Replace 'h' with 'r' → "rorse" 2. Delete 'r' → "rose" 3. Delete 'e' → "ros" The algorithm recursively compares characters from the end of both strings, exploring insert, delete, and replace operations when characters differ, and memoizes results to avoid redundant computations.

Approach

Straightforward Solution

A brute-force recursive approach tries all possible operations at each mismatch, leading to exponential time complexity due to repeated subproblems.

Core Observation

The minimum edit distance between prefixes of the two strings depends on the minimum edit distances of smaller prefixes, revealing overlapping subproblems and optimal substructure.

Path to Optimal

Preview

Recognizing the problem's overlapping subproblems and optimal substructure suggests dynamic programming…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Use a top-down recursive DP with memoization. The dp(i, j) function returns the minimum operations to convert word1[0.…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(m * n)

Each state (i, j) representing prefixes of word1 and word2 is computed once and stored in memo. There are m * n such states, and each computation does O(1) work.

Space

O(m * n)

The memoization dictionary stores results for all pairs of indices (i, j), requiring O(m * n) auxiliary space. The recursion stack depth is at most O(m + n), which is dominated by the memo size.

Pattern Spotlight

Dynamic Programming (Top-Down Memoization for Sequence Alignment)

When a problem asks for minimum operations to transform one sequence into another with insert/delete/replace, model it as a state machine over indices and use memoized recursion to avoid recomputation of overlapping subproblems.

Solution

Python

1class Solution:
  def minDistance(self, word1: str, word2: str) -> int:
      memo = {}
4
      def dp(i, j):
          if i < 0:
              return j + 1
          if j < 0:
              return i + 1
          if (i, j) in memo:
              return memo[(i, j)]
          
          if word1[i] == word2[j]:
              result = dp(i - 1, j - 1)
          else:
              insert = dp(i, j - 1)
              delete = dp(i - 1, j)
              replace = dp(i - 1, j - 1)
              result = 1 + min(insert, delete, replace)
          
          memo[(i, j)] = result
          return result
23
      return dp(len(word1) - 1, len(word2) - 1)

Step-by-Step Solution

Implement Base Cases for Empty Prefixes

6if i < 0:
7    return j + 1
8if j < 0:
9    return i + 1

Objective

To handle the scenarios where one string prefix is empty, requiring insertions or deletions equal to the length of the other prefix.

Key Insight

When one index is less than zero, it means one string is fully consumed. The minimum operations to convert an empty string to a prefix of length j is j insertions (or deletions if the other string is empty). This base case anchors the recursion and prevents invalid index access.

Interview Quick-Check

Core Logic

Base cases return the length of the remaining prefix of the other string, representing the minimal insert/delete operations needed.

State & Boundaries

Check for i < 0 or j < 0 to handle empty prefix conditions correctly.

Use Memoization to Avoid Redundant Computations

To cache and reuse results of subproblems identified by indices (i, j) to prevent exponential recursion.

Recursively Compute Edit Distance with Character Comparison

To recursively compute the minimum edit distance by comparing characters and exploring insert, delete, and replace operations when characters differ.

2 more steps with full analysis available on Pro.

Line Analysis

This solution has 6 Critical lines interviewers watch for.

Line 19 Critical

result = 1 + min(insert, delete, replace)

Calculate minimal cost among insert, delete, and replace plus one operation.

This min operation is the heart of the DP recurrence; it tries all possible edit operations and picks the one with the least cost, guaranteeing the minimal edit distance.

Line 6 Critical

if i < 0:

Return the number of insertions needed when word1 prefix is empty.

If i < 0, word1 is empty, so converting to word2[:j+1] requires j+1 insertions, which is the minimal operation count.

Line 8 Critical

if j < 0:

Return the number of deletions needed when word2 prefix is empty.

If j < 0, word2 is empty, so converting word1[:i+1] to empty requires i+1 deletions, the minimal operation count.

Full line-by-line criticality + rationale for all 17 lines available on Pro.

Test Your Understanding

Why does memoization reduce the time complexity from exponential to polynomial in this problem?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Edit Distance from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Edit Distance drill

or drill a free problem

1	`class Solution:`
2	`def minDistance(self, word1: str, word2: str) -> int:`
3	`memo = {}`
4
5	`def dp(i, j):`
6	`if i < 0:`
7	`return j + 1`
8	`if j < 0:`
9	`return i + 1`
10	`if (i, j) in memo:`
11	`return memo[(i, j)]`
12
13	`if word1[i] == word2[j]:`
14	`result = dp(i - 1, j - 1)`
15	`else:`
16	`insert = dp(i, j - 1)`
17	`delete = dp(i - 1, j)`
18	`replace = dp(i - 1, j - 1)`
19	`result = 1 + min(insert, delete, replace)`
20
21	`memo[(i, j)] = result`
22	`return result`
23
24	`return dp(len(word1) - 1, len(word2) - 1)`

6	`if i < 0:`
7	`return j + 1`
8	`if j < 0:`
9	`return i + 1`