Edit Distance: 2D DP Step by Step

Edit Distance is the gold-standard 2D DP problem. There are exactly three allowed operations, exactly three transitions, and exactly one recurrence. Once you have written it correctly once, you have written Longest Common Subsequence, Distinct Subsequences, Interleaving String, and Regular Expression Matching once too. The pattern transfers.

The Problem

Given two strings word1 and word2, return the minimum number of operations to convert word1 into word2. Each operation is one of:

• Insert a character.
• Delete a character.
• Replace one character with another.

This minimum is the Levenshtein distance.

Intuition

Let dp[i][j] be the edit distance between the first i characters of word1 and the first j characters of word2. If the two trailing characters match, no operation is needed at the end, so dp[i][j] = dp[i-1][j-1]. Otherwise, the last operation must be one of: delete the trailing char of word1 (drop to dp[i-1][j] + 1), insert a char into word1 to match (drop to dp[i][j-1] + 1), or replace it (drop to dp[i-1][j-1] + 1). We take the min. Base cases follow from converting against an empty string: dp[0][j] = j insertions, dp[i][0] = i deletions.

Explanation with Example

Convert "horse" to "ros".

The DP table fills as follows (rows = horse, cols = ros):

        ''  r  o  s
  ''     0  1  2  3
  h      1  1  2  3
  o      2  2  1  2
  r      3  2  2  2
  s      4  3  3  2
  e      5  4  4  3

Final answer: dp[5][3] = 3. One witnessing edit sequence: replace h with r, delete r, delete e. Three operations.

The replace step at dp[1][1] = 1 is the most instructive cell to inspect — it pulls from dp[0][0] = 0 and adds one.

           ""   r    o    s
 ""      0    1    2    3
 h       1    1    2    3
 o       2    2    1    2
 r       3    2    2    2
 s       4    3    3    2
 e       5    4    4    3

Three choices feed dp[i][j]:
delete  : dp[i-1][j]   + 1
insert  : dp[i][j-1]   + 1
replace : dp[i-1][j-1] + (chars differ)

Code

The full 2D table for clarity. A rolling-array version drops space to O(n) by keeping only the previous row.

def minDistance(word1, word2):
    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]

class Solution {
    public int minDistance(String word1, String word2) {
        int m = word1.length(), n = word2.length();
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 0; i <= m; i++) dp[i][0] = i;
        for (int j = 0; j <= n; j++) dp[0][j] = j;
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = 1 + Math.min(dp[i - 1][j - 1],
                                            Math.min(dp[i - 1][j], dp[i][j - 1]));
                }
            }
        }
        return dp[m][n];
    }
}

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    int minDistance(string word1, string word2) {
        int m = word1.size(), n = word2.size();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
        for (int i = 0; i <= m; i++) dp[i][0] = i;
        for (int j = 0; j <= n; j++) dp[0][j] = j;
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                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 - 1], dp[i - 1][j], dp[i][j - 1]});
                }
            }
        }
        return dp[m][n];
    }
};

Edge Cases

• Either string empty — answer equals the length of the other string. The base row and column handle this.
• Identical strings — the diagonal stays at zero throughout. Worth confirming with a quick mental run.
• Strings that share no characters — every cell except the base row/column hits the three-way min.
• Unicode characters that are visually similar but encode differently — the algorithm operates on code points, not glyphs. If interviewing for a localization-heavy team, mention normalization.

Complexity Analysis

Time is O(m * n) for both the 2D and rolling-array versions. Space is O(m * n) for the full table and O(min(m, n)) if you allocate the rolling array along the shorter dimension. The naive recursion is exponential without memoization and O(m * n) with it.

If “O(m * n) DP” is starting to feel like a familiar shape, that is the point — see Classic DP Problems for several siblings.

How to Explain It in an Interview

Start with the operations. Define dp[i][j] precisely. Articulate base cases explicitly — these are where candidates typically blow it. Walk through the recurrence for both the match case and the mismatch case, naming each of the three transitions (delete = up, insert = left, replace = diagonal).

Mention the rolling array as the immediate optimization. If asked whether you can do better than O(m * n), say “Not in general, though there is a Hyyro-Ukkonen bit-parallel algorithm for small alphabets — not interview-relevant.” This shows breadth without rambling.

Related Problems

• Longest Common Subsequence (same shape, different recurrence)
• Delete Operation for Two Strings
• Interleaving String
• Distinct Subsequences

Once you can flip between these by changing only the recurrence body, you have internalized the 2D string DP template.

Wrap up

Edit Distance is the boss fight of 2D DP and the friendliest one to prepare for, because everything generalizes from it. Practice writing the table by hand for a small example; the muscle memory of “diagonal, up, left, plus one” is what carries you through the trickier follow-ups. If the recurrence still feels foreign, anchor it in the DP introduction first and come back.