dp dp[i][j] = edits to turn word1.substring(i) into word2.substring(j) · ↓ delete · → insert · ↘ replace or keep
public int minDistance(String word1, String word2) { int m = word1.length(); int n = word2.length(); int[][] dp = new int[m + 1][n + 1]; for (int j = 0; j <= n; j++) { dp[m][j] = n - j; // insert the rest } for (int i = 0; i <= m; i++) { dp[i][n] = m - i; // delete the rest } for (int i = m - 1; i >= 0; i--) { for (int j = n - 1; j >= 0; j--) { if (word1.charAt(i) == word2.charAt(j)) { dp[i][j] = dp[i + 1][j + 1]; } else { dp[i][j] = 1 + Math.min(dp[i + 1][j], Math.min(dp[i][j + 1], dp[i + 1][j + 1])); } } } return dp[0][0];}
- i, j
- —
- word1.charAt(i)
- —
- word2.charAt(j)
- —
- dp[i][j]
- —
Why it works
- Brute force tries all three edits at every mismatch and recurses: about 3m+n calls, most of them on the same pair of suffixes over and over.
- Only suffixes matter. Once
word1.substring(0, i)already matchesword2.substring(0, j), the rest is the subproblem(i, j). Equal first letters cost nothing (↘). Otherwise pay 1 and pick the cheapest: deleteword1.charAt(i)(↓), insertword2.charAt(j)(→), or replace one with the other (↘). - Fill from the bottom-right. The ∅ row says "word1 is used up: insert the rest of word2"; the ∅ column says "word2 is done: delete the rest of word1". Each of the (m+1)·(n+1) cells reads three filled neighbours: O(m·n) time and space.
- Pitfall: on a match, copy the diagonal; do not take
1 + min(...). And the base cases aren − jandm − i, not 0: an empty suffix against a non-empty one still costs edits. - Space: each row reads only the row below, so two rows of n+1 cells are enough. Related: Longest Common Subsequence (1143) fills the same table with a max instead of a min.