Edit Distance
Problem statement
Given two strings word1 and word2, return the minimum number of single-character edits needed to turn word1 into word2. An edit is one of:
- insert a character,
- delete a character,
- replace one character with another.
This number is the Levenshtein distance. CLIs that answer a mistyped command with "did you mean ...?" rely on distances like this to find the closest known command.
Examples
Example 1
Input: word1 = "kubectl", word2 = "kubecfg"
Output: 2
Explanation: Replace t with f and l with g.
Example 2
Input: word1 = "", word2 = "ssh"
Output: 3
Explanation: Insert all three characters.
Hints
Approach
One row plus a saved diagonal. Each cell needs the cell above, the cell to the left and the diagonal. Keep one array row for the previous row. While sweeping a new row left to right, save the old row[j] before overwriting it; that saved value is the diagonal for the next column. Memory drops to O(n).
O(m · n)Space O(n)def min_distance(word1, word2): n = len(word2) row = list(range(n + 1)) # distances from "" to prefixes of word2 for i, a in enumerate(word1, start=1): diag, row[0] = row[0], i for j in range(1, n + 1): above = row[j] if a == word2[j - 1]: row[j] = diag else: row[j] = 1 + min(above, row[j - 1], diag) diag = above return row[n] print(min_distance("kubectl", "kubecfg"))print(min_distance("", "ssh"))Follow-up questions
- Return the actual list of edits, not only their count.
- Count swapping two adjacent characters as a single edit (Damerau-Levenshtein). What extra case does the recurrence need?
Frequently asked questions
Fuzzy matching is common in tooling: suggesting the closest command or flag after a typo, matching a hostname or service name that is almost right, or grouping near-identical log messages. Edit distance is the standard measure, and it is one of the best-known 2-D DP problems in SWE-style loops.
dp[i-1][j] means word1's last character was deleted, since i-1 characters of word1 now match j of word2. dp[i][j-1] means a character was inserted to match word2[j-1]. dp[i-1][j-1] with +1 is a replace. The code only needs the minimum, but naming them helps when you reconstruct the edits.
Computing the distance to every candidate is fine for a few hundred. For large vocabularies, you can stop a row early once all its values exceed the best distance so far, restrict the band around the diagonal, or index words with a BK-tree, which prunes candidates using the triangle inequality.