# Edit Distance: A Dynamic Programming Walkthrough **Edit Distance (LeetCode 72)** asks for the minimum number of insertions, deletions and substitutions that turn one word into another. It's the textbook two-string DP and a good template for many others. ## Define the state `dp[i][j]` = minimum edits to turn the first `i` characters of `a` into the first `j` characters of `b`. - If `a[i-1] == b[j-1]`: `dp[i][j] = dp[i-1][j-1]`. - Otherwise: `1 + min(dp[i-1][j]` (delete), `dp[i][j-1]` (insert), `dp[i-1][j-1]` (replace)`)`. - Base cases: `dp[i][0] = i`, `dp[0][j] = j`. ```python def min_distance(a, b): prev = list(range(len(b) + 1)) for i in range(1, len(a) + 1): cur = [i] + [0] * len(b) for j in range(1, len(b) + 1): if a[i-1] == b[j-1]: cur[j] = prev[j-1] else: cur[j] = 1 + min(prev[j], cur[j-1], prev[j-1]) prev = cur return prev[-1] ``` Time O(mn); space O(n) with the rolling row. ## How to present it 1. Start from recursion: "compare the last characters; three choices if they differ." 2. Point out the overlapping subproblems and add memoisation. 3. Convert to the bottom-up table, then compress to one row. Walking through those steps out loud is exactly what interviewers mean by "show your thought process." ## Same template, other problems Longest Common Subsequence (1143), Delete Operation for Two Strings (583), and One Edit Distance (161), which has an O(n) shortcut. --- *Disclosure: I help build [Linkjob AI](https://www.linkjob.ai/), an AI interview helper.*