# Edit Distance

- **Canonical ID**: `edit-distance`
- **Canonical URL**: https://dsacheatsheet.com/problems/edit-distance
- **Difficulty**: medium
- **Patterns**: 2D DP, Strings
- **Version**: 1.0.0 (verified 2026-11-11T21:20:00Z)
- **Original Problem**: https://leetcode.com/problems/edit-distance/

## 1. Core Invariant / The Trick

Levenshtein recurrence on rolling 1D row: if `w1[i] == w2[j]`, inherit `diag`; otherwise `1 + min(dp[j] /*delete*/, dp[j-1] /*insert*/, diag /*replace*/)`. Remember `dp[0] = i` on each row start.

## 2. Complexity Bounds & Proof

- **Time Complexity**: `O(M * N)`
- **Space Complexity**: `O(N)`
- **Proof**: Evaluates all prefix edit pairs `(i, j)` updating a single row plus scalar `diag` backup.

## 3. Minimal Idiomatic Code

### Python
```python
def minDistance(word1: str, word2: str) -> int:
    if len(word1) < len(word2):
        word1, word2 = word2, word1
    dp = list(range(len(word2) + 1))
    for i, c1 in enumerate(word1, 1):
        diag = dp[0]
        dp[0] = i
        for j, c2 in enumerate(word2, 1):
            up = dp[j]
            dp[j] = diag if c1 == c2 else 1 + min(up, dp[j - 1], diag)
            diag = up
    return dp[-1]
```

### TypeScript
```typescript
export function minDistance(word1: string, word2: string): number {
  if (word1.length < word2.length) [word1, word2] = [word2, word1];
  const dp = Array.from({ length: word2.length + 1 }, (_, j) => j);
  for (let i = 1; i <= word1.length; i++) {
    let diag = dp[0];
    dp[0] = i;
    for (let j = 1; j <= word2.length; j++) {
      const up = dp[j];
      dp[j] = word1[i - 1] === word2[j - 1] ? diag : 1 + Math.min(up, dp[j - 1], diag);
      diag = up;
    }
  }
  return dp[word2.length];
}
```

### C++
```cpp
int minDistance(string w1, string w2) {
    if (w1.size() < w2.size()) swap(w1, w2);
    vector<int> dp(w2.size() + 1);
    iota(dp.begin(), dp.end(), 0);
    for (size_t i = 1; i <= w1.size(); ++i) {
        int diag = dp[0]; dp[0] = i;
        for (size_t j = 1; j <= w2.size(); ++j) {
            int up = dp[j];
            dp[j] = (w1[i - 1] == w2[j - 1]) ? diag : 1 + min({up, dp[j - 1], diag});
            diag = up;
        }
    }
    return dp.back();
}
```

### Java
```java
int minDistance(String w1, String w2) {
    if (w1.length() < w2.length()) { String t = w1; w1 = w2; w2 = t; }
    int[] dp = new int[w2.length() + 1];
    for (int j = 0; j < dp.length; j++) dp[j] = j;
    for (int i = 1; i <= w1.length(); i++) {
        int diag = dp[0]; dp[0] = i;
        for (int j = 1; j <= w2.length(); j++) {
            int up = dp[j];
            dp[j] = w1.charAt(i - 1) == w2.charAt(j - 1) ? diag : 1 + Math.min(up, Math.min(dp[j - 1], diag));
            diag = up;
        }
    }
    return dp[w2.length()];
}
```

### Go
```go
func minDistance(w1, w2 string) int {
    if len(w1) < len(w2) { w1, w2 = w2, w1 }
    dp := make([]int, len(w2)+1)
    for j := range dp { dp[j] = j }
    for i := 1; i <= len(w1); i++ {
        diag := dp[0]; dp[0] = i
        for j := 1; j <= len(w2); j++ {
            up := dp[j]
            if w1[i-1] == w2[j-1] { dp[j] = diag } else { dp[j] = 1 + min(up, min(dp[j-1], diag)) }
            diag = up
        }
    }
    return dp[len(w2)]
}
```

## 4. Failure Modes & Interview Follow-ups

### Pitfalls
- Neglecting to re-seed `dp[0] = i` before each row loses cost of deleting prefix `w1[:i]` to empty string `""`.
- Overwriting `dp[j]` without caching `diag` into `prev` corrupts replacement transitions.

### Follow-ups
- Myers diff / patience diff optimizes when differences are small (O((M+N)*D)) — used inside git diff and `fast-diff`.