Coding Interview PatternsEdit Distance
MediumDynamic Programming

Edit Distance

Explanation & Solution

Practice Problem

Description

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

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

Output: 3

Explanation:

horse -> rorse (replace 'h' with 'r')

rorse -> rose (remove 'r')

rose -> ros (remove 'e')

Constraints

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

Approach

Dynamic Programming pattern

1. Define the DP Table

  • Create a 2D array dp of size (m+1) x (n+1) where m = word1.length and n = word2.length
  • dp[i][j] represents the minimum edit distance between word1[0..i-1] and word2[0..j-1]

2. Set Up Base Cases

  • dp[i][0] = i: converting a string of length i to an empty string requires i deletions
  • dp[0][j] = j: converting an empty string to a string of length j requires j insertions

3. Fill the Table Row by Row

  • For each pair of characters word1[i-1] and word2[j-1]:
  • If they match: dp[i][j] = dp[i-1][j-1] (no operation needed)
  • If they differ: take the minimum of three operations plus 1:
  • dp[i-1][j] + 1: delete from word1
  • dp[i][j-1] + 1: insert into word1
  • dp[i-1][j-1] + 1: replace in word1

4. Return the Result

  • dp[m][n] contains the minimum number of operations to convert the full word1 into word2

Key Insight

  • Each cell depends on at most three neighbors: left, top, and top-left diagonal
  • The recurrence captures all three edit operations elegantly in one formula
Time
O(m * n) where m and n are the lengths of the two strings
Space
O(m * n) for the DP table (can be optimized to O(min(m, n)) with rolling arrays)

Solution Code

Previous
Target Sum
Next
Regular Expression Matching