Example 1
ready- Input
word1 = "horse" word2 = "ros"- Expected
3- Why
- three edits are enough, and no two-edit route exists
Edit Distance
50 min · minDistance()A typo fixer needs more than a yes-or-no answer. It needs to know how far one word is from another.
Given lowercase strings word1 and word2, return the fewest single-character edits
needed to turn word1 into word2. You may perform three kinds of edit:
- insert one character,
- delete one character, or
- replace one character with another.
The Levenshtein distance is the minimum number of those edits needed for a transformation. Each edit costs one, and you may apply edits in any order.
An empty string is valid. Turning an empty string into a word requires one insertion per character; turning a word into an empty string requires the matching number of deletions.
Constraints
0 <= word1.length <= 2000 <= word2.length <= 200- Both strings contain only lowercase English letters.
Hints
Compare the next characters
If word1[i] == word2[j], those characters already agree, so move past both at no
cost. Otherwise, model the first edit and solve the remaining suffixes.
Name the three branches
An insertion advances only j, a deletion advances only i, and a replacement
advances both. Add one to the cheapest resulting state.
Build from empty prefixes
Let a table cell store the distance between two prefixes. Row zero and column zero are known: converting to or from an empty prefix costs the other prefix's length.
Follow-up
Could you return one shortest sequence of edits, not just its length?
Visible cases
Examples
Example 2
ready- Input
word1 = "intention" word2 = "execution"- Expected
5- Why
- the shortest transformation uses five edits
Example 3
ready- Input
word1 = "" word2 = "abc"- Expected
3- Why
- insert a, b, and c
Interview signal
Asked at
AmazonGoogleMicrosoft
Every mismatch offers three edits, so a raw search branches fast. The escape hatch is that the same pair of suffixes keeps reappearing.
Let m = len(word1) and n = len(word2).
Memoized edit search
Define the state (i, j) as the minimum edits needed to turn word1[i:] into
word2[j:]. Memoization means caching that answer; the recursive search then becomes
top-down dynamic programming (DP).
When the current characters match, move past both for free. Otherwise try the first edit:
- insertion: keep
i, advancej; - deletion: advance
i, keepj; - replacement: advance both.
from functools import cache
def min_distance(word1: str, word2: str) -> int:
@cache
def distance(i: int, j: int) -> int:
if i == len(word1):
return len(word2) - j
if j == len(word2):
return len(word1) - i
if word1[i] == word2[j]:
return distance(i + 1, j + 1)
insert = distance(i, j + 1)
delete = distance(i + 1, j)
replace = distance(i + 1, j + 1)
return 1 + min(insert, delete, replace)
return distance(0, 0)Time O(mn) because each pair of positions is solved once. Space O(mn) for the
cache, with an additional recursion depth of at most m + n.
Rolling-row edit DP
Turn the same recurrence around. The DP state dp[i][j] is the distance between the
first i characters of one word and the first j characters of the other.
- Matching final characters copy the diagonal value.
- A mismatch costs
1 + min(up, left, diagonal)for delete, insert, and replace.
Only the previous row is needed. Put the shorter word across the columns to keep that row small.
def min_distance(word1: str, word2: str) -> int:
if len(word1) < len(word2):
longer, shorter = word2, word1
else:
longer, shorter = word1, word2
previous = list(range(len(shorter) + 1))
for i, left_char in enumerate(longer, start=1):
current = [i]
for j, right_char in enumerate(shorter, start=1):
if left_char == right_char:
current.append(previous[j - 1])
else:
current.append(
1 + min(previous[j], current[j - 1], previous[j - 1])
)
previous = current
return previous[-1]Time O(mn) because every prefix pair is considered. Space O(min(m, n)) for two rolling rows.
This DP works because the best transformation of larger prefixes must finish through one of exactly those three neighboring states.
Loading editor
Console
ready to runReady to run.
3 cases are queued.
Visible testcase
Case 1
Expected
3
Run: visible + custom · Submit: full suite