Edit Distance (Levenshtein Distance)

Compute the minimum number of insertions, deletions, and substitutions to convert one string into another.

dynamic-programming strings levenshtein-distance

Given two strings `a` and `b`, return the **edit distance** between them. The edit distance is the minimum number of operations required to convert `a` into `b`, where an operation is one of:
- Insert a character
- Delete a character
- Replace a character

Implement the function `edit_distance(a: str, b: str) -> int` that returns the edit distance.

**Example:**
- `edit_distance("kitten", "sitting")` → 3
- `edit_distance("", "abc")` → 3 (insert three characters)
- `edit_distance("abc", "")` → 3 (delete three characters)

Constraints

- `0 <= len(a), len(b) <= 1000`
- Strings consist of lowercase English letters and/or spaces.
- The expected time complexity is O(len(a) * len(b)) or better.

Example

>>> edit_distance("kitten", "sitting")
3
>>> edit_distance("", "abc")
3
>>> edit_distance("ABC", "xyz")
3

25 points ~30 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Define dp[i][j] as the edit distance between a[:i] and b[:j].

Initialize dp[i][0] = i and dp[0][j] = j.

If a[i-1] == b[j-1], then dp[i][j] = dp[i-1][j-1]; otherwise, take the minimum of insert, delete, and replace and add 1.

You can use two rows to optimize space to O(min(len(a), len(b))).

Test Results

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