Edit Distance
The briefingthe full drill, in my own words
The drill: Find the fewest single-character insertions, deletions, and substitutions needed to turn one word into another.
Two words show up, and the job is finding the smallest number of single-character edits — inserting a letter, deleting a letter, or swapping one letter for another — that turns the first word into the second.
Each edit touches exactly one character and counts as one step regardless of which of the three operations it is. Matching characters that already line up cost nothing and never need to be touched.
Either word can be empty, and letters may repeat freely within or across the two words — the only thing being measured is the shortest chain of edits that bridges them.
- either word may be empty; an empty word costs its partner's full length to reach
- words hold ordinary letters, lengths staying in the low thousands at most
- insert, delete, and substitute each cost exactly one edit — no partial credit
- the answer is the single smallest edit count, not the edit sequence itself
The hintstake only what you need
HINT 1 THE NUDGE
Compare the two words from their last characters backward. If those two characters already match, that pair costs nothing — the problem reduces to the same question on both words with that character stripped off.
HINT 2 THE STRUCTURE
When the last characters differ, exactly one edit has to happen at that position — but which one? Try all three: delete from the first word, insert to match the second, or substitute it, and recurse on whichever leftover pair results.
HINT 3 ONE STEP FROM THE ANSWER
dp(i, j) = dp(i−1, j−1) when word1[i−1] == word2[j−1]; otherwise 1 + min(dp(i−1, j), dp(i, j−1), dp(i−1, j−1)) — deletion, insertion, substitution. Base cases: dp(i, 0) = i, dp(0, j) = j.
Coach's boardthe pattern, step by step
word1='ab', word2='ba'. Base cases: dp[0][j]=j inserts build word2's prefix from nothing; dp[i][0]=i deletes empty word1's prefix.
The splitstwo paces, two languages
class Solution:
def minDistance(self, word1: str, word2: str) -> int:
n, m = len(word1), len(word2)
dp = [[0] * (m + 1) for _ in range(n + 1)]
for i in range(n + 1):
dp[i][0] = i
for j in range(m + 1):
dp[0][j] = j
for i in range(1, n + 1):
for j in range(1, m + 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[n][m]class Solution:
def minDistance(self, word1: str, word2: str) -> int:
def rec(i, j):
if i == 0:
return j
if j == 0:
return i
if word1[i - 1] == word2[j - 1]:
return rec(i - 1, j - 1)
return 1 + min(
rec(i - 1, j), # delete from word1
rec(i, j - 1), # insert into word1
rec(i - 1, j - 1), # substitute
)
return rec(len(word1), len(word2))class Solution {
public int minDistance(String word1, String word2) {
int n = word1.length(), m = word2.length();
int[][] dp = new int[n + 1][m + 1];
for (int i = 0; i <= n; i++) dp[i][0] = i;
for (int j = 0; j <= m; j++) dp[0][j] = j;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; 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], Math.min(dp[i][j - 1], dp[i - 1][j - 1]));
}
}
}
return dp[n][m];
}
}class Solution {
private String word1, word2;
public int minDistance(String word1, String word2) {
this.word1 = word1;
this.word2 = word2;
return rec(word1.length(), word2.length());
}
private int rec(int i, int j) {
if (i == 0) return j;
if (j == 0) return i;
if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
return rec(i - 1, j - 1);
}
return 1 + Math.min(rec(i - 1, j), Math.min(rec(i, j - 1), rec(i - 1, j - 1)));
}
}✓ CHIP-TIMEDALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED