# Edit Distance Dynamic Programming Implementation: A Complete Guide with Code Examples

> Implement edit distance dynamic programming with code examples. Discover O(nxm) time and O(m) space optimization using a 2D dp table to track minimum operations.

- Repository: [Yudong Jin/hello-algo](https://github.com/krahets/hello-algo)
- Tags: how-to-guide
- Published: 2026-02-25

---

**The edit distance dynamic programming solution uses a 2D table `dp[i][j]` to track minimum operations, achieving O(n×m) time and O(m) space through row-wise optimization.**

The edit distance (Levenshtein distance) problem computes the minimum number of single-character insertions, deletions, or substitutions required to transform string `s` into string `t`. The `krahets/hello-algo` repository provides complete implementations in multiple languages, demonstrating both the classic dynamic programming approach and memory-optimized variants.

## Understanding the Edit Distance Problem

The problem requires calculating the cheapest sequence of operations to convert one string into another. Each operation—inserting a character, deleting a character, or replacing a character—carries a unit cost. The solution must explore all possible alignment paths between the two strings while avoiding the exponential complexity of naive recursion by caching intermediate results.

## Edit Distance Dynamic Programming State Definition

The dynamic programming approach defines the state as a two-dimensional array where each cell represents a subproblem solution.

**State:** `dp[i][j]` stores the minimum edit distance to transform the first `i` characters of `s` into the first `j` characters of `t`.

**Boundary Conditions:**
- `dp[0][j] = j` — Transforming an empty string into the first `j` characters requires `j` insertions
- `dp[i][0] = i` — Transforming the first `i` characters into an empty string requires `i` deletions

## State Transition and Recurrence Relation

The transition logic compares characters at positions `s[i-1]` and `t[j-1]` (using zero-based indexing for strings but one-based for the DP table).

**Case 1: Characters match**
If `s[i-1] === t[j-1]`, no operation is needed:

```

dp[i][j] = dp[i-1][j-1]

```

**Case 2: Characters differ**
If characters mismatch, choose the minimum cost among three operations plus one:

```

dp[i][j] = 1 + min(
    dp[i][j-1],    // Insert: align t[j-1] by inserting into s
    dp[i-1][j],    // Delete: remove s[i-1]
    dp[i-1][j-1]   // Replace: change s[i-1] to t[j-1]
)

```

## Space Optimization for Edit Distance DP

The standard implementation uses O(n×m) space to store the full table. However, the recurrence only depends on the current row and the previous row. This allows reducing space complexity to **O(m)** where `m` is the length of string `t`.

**Optimization technique:**
- Maintain a single 1D array `dp[0…m]` representing the current row
- Use a temporary variable `leftUp` to store the diagonal value `dp[i-1][j-1]` before it gets overwritten
- Update the array left-to-right, shifting the diagonal value through `leftUp`

This approach is implemented in the `editDistanceDPComp` functions across language implementations in the repository.

## Complete Code Implementation

The `krahets/hello-algo` repository provides the edit distance dynamic programming solution in multiple languages. Below are the TypeScript and Zig implementations demonstrating both the full table and space-optimized approaches.

### TypeScript Implementation

Located in [`codes/typescript/chapter_dynamic_programming/edit_distance.ts`](https://github.com/krahets/hello-algo/blob/main/codes/typescript/chapter_dynamic_programming/edit_distance.ts), this implementation provides four variants: DFS, memoized DFS, classic DP, and space-optimized DP.

```typescript
// Classic DP implementation with O(n*m) space
function editDistanceDP(s: string, t: string): number {
    const n = s.length, m = t.length;
    const dp = Array.from({ length: n + 1 }, () =>
        Array.from({ length: m + 1 }, () => 0)
    );

    // Boundary conditions: first row and column
    for (let i = 1; i <= n; i++) dp[i][0] = i;
    for (let j = 1; j <= m; j++) dp[0][j] = j;

    // Fill the DP table
    for (let i = 1; i <= n; i++) {
        for (let j = 1; j <= m; j++) {
            if (s[i - 1] === t[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                dp[i][j] = Math.min(
                    dp[i][j - 1],    // insert
                    dp[i - 1][j],    // delete
                    dp[i - 1][j - 1] // replace
                ) + 1;
            }
        }
    }
    return dp[n][m];
}

```

### Zig Implementation

The Zig version in `codes/zig/chapter_dynamic_programming/edit_distance.zig` demonstrates space optimization using compile-time parameters and manual memory management.

```zig
// Space-optimized DP with O(m) space
fn editDistanceDPComp(comptime s: []const u8, comptime t: []const u8) i32 {
    comptime var n = s.len;
    comptime var m = t.len;
    var dp = [_]i32{0} ** (m + 1);

    // Initialize first row (transform empty s to first j chars of t)
    for (1..m + 1) |j| dp[j] = @intCast(j);

    // Process each row
    for (1..n + 1) |i| {
        var leftup = dp[0];   // Stores dp[i-1][j-1] (diagonal)
        dp[0] = @intCast(i);  // First column: delete i chars
        
        for (1..m + 1) |j| {
            const temp = dp[j];
            if (s[i - 1] == t[j - 1]) {
                dp[j] = leftup;  // Characters match, no operation needed
            } else {
                dp[j] = @min(@min(dp[j - 1], dp[j]), leftup) + 1;
            }
            leftup = temp;  // Update diagonal for next iteration
        }
    }
    return dp[m];
}

```

## How to Run the Code Examples

To execute the edit distance dynamic programming implementations from the `hello-algo` repository:

**TypeScript:**

```bash
cd codes/typescript/chapter_dynamic_programming
npx ts-node edit_distance.ts

```

**Zig:**

```bash
cd codes/zig/chapter_dynamic_programming
zig build-exe edit_distance.zig
./edit_distance

```

Both programs compute the edit distance between sample strings (typically `"bag"` and `"pack"`) and output the minimum number of operations required.

## Summary

- **State Definition:** The edit distance dynamic programming solution uses `dp[i][j]` to represent the minimum operations needed to transform the first `i` characters of string `s` into the first `j` characters of string `t`.
- **Boundary Conditions:** The first row `dp[0][j] = j` and first column `dp[i][0] = i` handle transformations involving empty strings through insertions or deletions.
- **Transition Logic:** When characters match, `dp[i][j] = dp[i-1][j-1]`; otherwise, take the minimum of insert, delete, or replace operations plus one.
- **Space Optimization:** The algorithm reduces space from O(n×m) to O(m) by maintaining only the current row and a temporary variable for the diagonal value, as implemented in `editDistanceDPComp` functions.

## Frequently Asked Questions

### What is the time and space complexity of the edit distance dynamic programming solution?

The standard implementation runs in **O(n×m)** time where `n` and `m` are the lengths of the two strings, and uses **O(n×m)** space to store the full DP table. The space-optimized version reduces this to **O(m)** time and space by keeping only the current row, as demonstrated in the `editDistanceDPComp` functions in both TypeScript and Zig implementations.

### How does the space-optimized edit distance algorithm work?

The space-optimized approach recognizes that computing `dp[i][j]` only requires the previous row (`dp[i-1][j]`), the current row's left neighbor (`dp[i][j-1]`), and the diagonal (`dp[i-1][j-1]`). By using a one-dimensional array of size `m+1` and a temporary variable `leftUp` to store the diagonal value before it gets overwritten, the algorithm achieves O(m) space while maintaining the same O(n×m) time complexity.

### Where can I find the complete edit distance implementations in the hello-algo repository?

The complete implementations are located in the `codes/` directory under `chapter_dynamic_programming/`. Specifically, the TypeScript version is at [`codes/typescript/chapter_dynamic_programming/edit_distance.ts`](https://github.com/krahets/hello-algo/blob/main/codes/typescript/chapter_dynamic_programming/edit_distance.ts) and the Zig version is at `codes/zig/chapter_dynamic_programming/edit_distance.zig`. The detailed algorithmic explanation resides in [`en/docs/chapter_dynamic_programming/edit_distance_problem.md`](https://github.com/krahets/hello-algo/blob/main/en/docs/chapter_dynamic_programming/edit_distance_problem.md).

### What is the difference between the standard DP and the DPComp variants in the hello-algo implementations?

The standard `editDistanceDP` function implements the classic two-dimensional dynamic programming approach with explicit `dp[i][j]` table storage, making the logic easier to understand and debug. The `editDistanceDPComp` variant (where "Comp" stands for compressed or compile-time optimized) implements the space-optimized O(m) algorithm using a single array and temporary variables. In the Zig implementation, `DPComp` also utilizes `comptime` parameters for potential compile-time evaluation, while both variants maintain identical mathematical correctness and time complexity.