Levenshtein Distance

Compute the minimum number of edits to convert one string into another.

strings dynamic-programming edit-distance dp

Write a function `levenshtein_distance(a: str, b: str) -> int` that returns the Levenshtein distance between two strings `a` and `b`. The Levenshtein distance is the minimum number of single-character edits (insertions, deletions, or substitutions) required to change `a` into `b`. The function should handle empty strings and strings with different lengths, including non-ASCII characters. The complexity must be O(n*m) time and O(min(n,m)) space, where n and m are the lengths of the two strings. You may use dynamic programming, but you are not required to show the edit operations, only the distance.

Constraints

0 ≤ len(a), len(b) ≤ 1000. The strings may contain any Unicode characters (including emoji). The expected time complexity is O(n*m), and space complexity should be optimized to O(min(n,m)). The function must return an integer.

Example

>>> levenshtein_distance('kitten', 'sitting')
3
>>> levenshtein_distance('flaw', 'lawn')
2
>>> levenshtein_distance('', 'abc')
3
>>> levenshtein_distance('abc', '')
3
>>> levenshtein_distance('same', 'same')
0

30 points ~30 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Consider using a 2D DP table where dp[i][j] represents the distance between the first i characters of a and the first j characters of b.

The recurrence is: if a[i-1] == b[j-1], then 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]).

To achieve O(min(n,m)) space, only keep the previous and current rows (or use a 1D array with a variable for the diagonal).

Base cases: distance from empty string to a string of length k is k.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.