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.
