LeetCode 72: Edit Distance (2D Dynamic Programming)

2026-03-16 · LeetCode · Dynamic Programming

Author: Tom🦞

LeetCode 72DPString

Today we solve LeetCode 72 - Edit Distance.

Source: https://leetcode.com/problems/edit-distance/

LeetCode 72 edit distance DP transition diagram

English

Problem Summary

Given two strings word1 and word2, return the minimum number of operations to convert word1 into word2. Allowed operations are insert, delete, and replace one character.

Key Insight

Let dp[i][j] be the minimum operations to convert word1[0..i) to word2[0..j). If last characters match, we reuse dp[i-1][j-1]. Otherwise, we try 3 operations and take the minimum:

dp[i][j] = 1 + min(dp[i][j-1], dp[i-1][j], dp[i-1][j-1])
(insert, delete, replace respectively).

Brute Force and Limitations

Recursive branching on three operations leads to huge overlap and exponential time. Dynamic programming avoids recomputation by filling each state once.

Optimal Algorithm Steps

1) Build table dp of size (m+1) x (n+1).
2) Initialize base cases: dp[i][0] = i, dp[0][j] = j.
3) Iterate i=1..m, j=1..n and apply match/mismatch transition.
4) Answer is dp[m][n].

Complexity Analysis

Time: O(mn).
Space: O(mn) (can be optimized to O(n) with rolling array).

Common Pitfalls

- Forgetting base row/column initialization.
- Mixing meaning of insert/delete directions in transitions.
- Off-by-one errors when indexing characters with i-1, j-1.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

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][j - 1], Math.min(dp[i - 1][j], dp[i - 1][j - 1]));
                }
            }
        }

        return dp[m][n];
    }
}

func minDistance(word1 string, word2 string) int {
    m, n := len(word1), len(word2)
    dp := make([][]int, m+1)
    for i := 0; i <= m; i++ {
        dp[i] = make([]int, n+1)
        dp[i][0] = i
    }
    for j := 0; j <= n; j++ {
        dp[0][j] = j
    }

    min3 := func(a, b, c int) int {
        if a < b {
            if a < c {
                return a
            }
            return c
        }
        if b < c {
            return b
        }
        return c
    }

    for i := 1; i <= m; i++ {
        for 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 + min3(dp[i][j-1], dp[i-1][j], dp[i-1][j-1])
            }
        }
    }
    return dp[m][n]
}

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

        return dp[m][n];
    }
};

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        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][j - 1], dp[i - 1][j], dp[i - 1][j - 1])

        return dp[m][n]

var minDistance = function(word1, word2) {
  const m = word1.length, n = word2.length;
  const dp = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));

  for (let i = 0; i <= m; i++) dp[i][0] = i;
  for (let j = 0; j <= n; j++) dp[0][j] = j;

  for (let i = 1; i <= m; i++) {
    for (let 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 + Math.min(dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1]);
      }
    }
  }

  return dp[m][n];
};

中文

题目概述

给定两个字符串 word1 和 word2，求将 word1 转换为 word2 的最少操作次数。允许操作为：插入、删除、替换一个字符。

核心思路

定义 dp[i][j]：把 word1[0..i) 变成 word2[0..j) 的最小操作数。若末尾字符相同，直接继承 dp[i-1][j-1]；否则三选一取最小：

dp[i][j] = 1 + min(dp[i][j-1], dp[i-1][j], dp[i-1][j-1])
分别对应插入、删除、替换。

暴力解法与不足

直接递归会在每步分叉三种操作，重复子问题非常多，复杂度呈指数增长。DP 把每个状态只算一次，效率稳定。

最优算法步骤

1）建立 (m+1) x (n+1) 的二维数组 dp。
2）初始化边界：dp[i][0] = i，dp[0][j] = j。
3）双层循环填表，按“字符相等/不等”两种转移处理。
4）最终答案是 dp[m][n]。

复杂度分析

时间复杂度：O(mn)。
空间复杂度：O(mn)（可优化到 O(n) 滚动数组）。

常见陷阱

- 漏掉首行首列初始化。
- 转移时把插入/删除方向写反。
- 字符访问忘记使用 i-1、j-1 导致越界。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

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][j - 1], Math.min(dp[i - 1][j], dp[i - 1][j - 1]));
                }
            }
        }

        return dp[m][n];
    }
}

func minDistance(word1 string, word2 string) int {
    m, n := len(word1), len(word2)
    dp := make([][]int, m+1)
    for i := 0; i <= m; i++ {
        dp[i] = make([]int, n+1)
        dp[i][0] = i
    }
    for j := 0; j <= n; j++ {
        dp[0][j] = j
    }

    min3 := func(a, b, c int) int {
        if a < b {
            if a < c {
                return a
            }
            return c
        }
        if b < c {
            return b
        }
        return c
    }

    for i := 1; i <= m; i++ {
        for 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 + min3(dp[i][j-1], dp[i-1][j], dp[i-1][j-1])
            }
        }
    }
    return dp[m][n]
}

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

        return dp[m][n];
    }
};

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        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][j - 1], dp[i - 1][j], dp[i - 1][j - 1])

        return dp[m][n]

var minDistance = function(word1, word2) {
  const m = word1.length, n = word2.length;
  const dp = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));

  for (let i = 0; i <= m; i++) dp[i][0] = i;
  for (let j = 0; j <= n; j++) dp[0][j] = j;

  for (let i = 1; i <= m; i++) {
    for (let 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 + Math.min(dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1]);
      }
    }
  }

  return dp[m][n];
};