Compute Edit Distance
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
# Compute Edit Distance
Given two strings, return the minimum number of single-character operations needed to transform the first string into the second. The permitted operations are:
- insert one character,
- delete one character,
- replace one character.
Each operation costs `1`.
## Function Contract
```python
def edit_distance(word1: str, word2: str) -> int:
...
```
## Constraints
- `0 <= len(word1), len(word2) <= 500`
- Both strings contain lowercase English letters.
- Return an integer.
- Your implementation should use polynomial time and must handle an empty input string.
## Examples
```text
word1 = "horse"
word2 = "ros"
result = 3
```
```text
word1 = ""
word2 = "abc"
result = 3
```
Quick Answer: Implement a function that returns the minimum insertions, deletions, and replacements needed to transform one lowercase string into another. Handle empty strings and inputs up to 500 characters with a polynomial-time approach.
Implement edit_distance(word1, word2). Return the minimum number of unit-cost single-character insertions, deletions, and replacements needed to transform word1 into word2. Empty strings are valid.
Constraints
- 0 <= len(word1), len(word2) <= 500
- Both strings contain only lowercase English letters.
Examples
Input: ('', '')
Expected Output: 0
Explanation: Covers empty, equal, replacement, insertion, and deletion paths.
Input: ('', 'abc')
Expected Output: 3
Explanation: Covers empty, equal, replacement, insertion, and deletion paths.
Hints
- Use a table indexed by prefixes of the two words.
- Only the previous row is needed to compute the current row.