HardDynamic programming

Edit Distance

Q: Why not Array.new(n + 1, Array.new(m + 1, -1))?

With a second argument, Array.new puts the same object in every slot, so every row would be one shared array and writing memo[2][3] would change all of them. The block form Array.new(n + 1) { Array.new(m + 1, -1) } runs the block once per row and gives each row its own array.

Q: Can I memoise with a Hash instead?

Yes: memo = Hash.new and memo[[i, j]] ||= ... is a common Ruby idiom, and a Hash.new { |h, (i, j)| h[[i, j]] = ... } default block can even hold the whole recursion. Each key is a new two-element array that must be hashed, though, so the nested Array with -1 is faster and uses less memory.

Q: Will the recursion hit SystemStackError?

The deepest chain is n + m calls, 600 frames at the size bound, which the default Ruby VM stack handles easily. Ruby stacks are smaller than JVM ones, so for words in the thousands use the table or the two-row loop.

Q: Is there a built-in Levenshtein in Ruby?

Not in core. DidYouMean::Levenshtein.distance(a, b) ships with Ruby for the did-you-mean suggestions and returns this number, and gems such as levenshtein-ffi or damerau-levenshtein are faster. On a practice problem you write the loop yourself.

Q: Why use bytes in the two-row version?

word[i] returns a new one-character String each time, so the inner loop allocates on every comparison. bytes turns the word into an Array of Integers once, and comparing two Integers allocates nothing. For lowercase ASCII each letter is exactly one byte; for Unicode use chars instead.

You get two strings, word1 and word2. You may change word1 one letter at a time with three operations: insert a letter anywhere, delete a letter, or replace a letter with a different one. Each operation costs 1. Return the smallest number of operations that turns word1 into word2.

Either string can be empty: turning a word into the empty string takes one delete per letter, and building a word from nothing takes one insert per letter. Two equal strings need 0 operations. Letters are compared exactly, and both strings hold lowercase English letters only.

Examples

Input

word1 = "lantern"
word2 = "pattern"

Output2WhyReplace the l with p and the first n with t; the a and the ending tern already match.

Input

word1 = "stone"
word2 = "tones"

Output2WhyDelete the leading s and insert an s at the end. Replacing letter by letter in place would cost 5, because every position differs.

Constraints

Size: 0 ≤ word1.length, word2.length ≤ 300
Letters: Lowercase English letters a to z
Cost: Insert, delete and replace each cost 1.
Time limit: 10 s per run, all cases

Run your code 2 more times to open the solutions. The idea sticks better after an attempt.

3 reference approaches in Python, from brute force to the one to reach for. Compare them with yours.

1 · Top-down: recurse on suffixes and cache each pair

O(n·m) time · O(n·m) space

dist(i, j) is the distance between the suffixes word1[i:] and word2[j:]. When one suffix is empty the answer is the length of the other. When the first letters match they cost nothing, so move both indices on. Otherwise try the three moves, delete (i + 1), insert (j + 1) and replace (both), and keep the cheapest plus one. Without @cache the three branches make this exponential; with it each of the (n + 1) × (m + 1) pairs is solved once. The recursion goes at most n + m frames deep, which fits under the default limit of 1000 for these sizes.

from functools import cache


def min_distance(word1: str, word2: str) -> int:
    n, m = len(word1), len(word2)

    @cache
    def dist(i: int, j: int) -> int:
        if i == n:
            return m - j  # insert the rest of word2
        if j == m:
            return n - i  # delete the rest of word1
        if word1[i] == word2[j]:
            return dist(i + 1, j + 1)
        return 1 + min(dist(i + 1, j), dist(i, j + 1), dist(i + 1, j + 1))

    return dist(0, 0)

2 · Bottom-up: fill the full (n+1) × (m+1) table

O(n·m) time · O(n·m) space

The same idea bottom-up on prefixes. d[i][j] is the distance between the first i letters of word1 and the first j of word2. Row 0 counts inserts and column 0 counts deletes. Every other cell copies the diagonal when the letters match, or takes one more than the smallest of the cell above (delete), the cell to the left (insert) and the diagonal (replace). Plain loops, no recursion limit, and the finished table can be walked back to recover the actual edits.

def min_distance(word1: str, word2: str) -> int:
    n, m = len(word1), len(word2)
    d = [[0] * (m + 1) for _ in range(n + 1)]
    for i in range(n + 1):
        d[i][0] = i  # delete i letters
    for j in range(m + 1):
        d[0][j] = j  # insert j letters
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if word1[i - 1] == word2[j - 1]:
                d[i][j] = d[i - 1][j - 1]
            else:
                d[i][j] = 1 + min(d[i - 1][j], d[i][j - 1], d[i - 1][j - 1])
    return d[n][m]

3 · Two rows over the shorter word

O(n·m) time · O(min(n, m)) space

recommended

Each row of the table reads only the row above, so keep two lists, prev and cur, and swap them after every row. The distance is symmetric (an insert one way is a delete the other way), so swap the words first to make the rows as short as the shorter word. The time stays O(n·m) and the memory drops to O(min(n, m)).

def min_distance(word1: str, word2: str) -> int:
    if len(word2) > len(word1):
        word1, word2 = word2, word1  # rows run over the shorter word
    m = len(word2)
    prev = list(range(m + 1))
    for i, a in enumerate(word1, 1):
        cur = [i] + [0] * m
        for j, b in enumerate(word2, 1):
            if a == b:
                cur[j] = prev[j - 1]
            else:
                cur[j] = 1 + min(prev[j], cur[j - 1], prev[j - 1])
        prev = cur
    return prev[m]

3 reference approaches in JavaScript, from brute force to the one to reach for. Compare them with yours.

1 · Top-down: recurse on suffixes and cache each pair

O(n·m) time · O(n·m) space

dist(i, j) is the distance between the suffixes starting at i in word1 and at j in word2. An empty suffix costs the length of the other one; matching first letters cost nothing; otherwise take one plus the cheapest of delete, insert and replace. The cache is a flat Int32Array of (n + 1) × (m + 1) slots filled with -1, indexed by i * (m + 1) + j, which is faster than a Map keyed by strings built from both indices.

function minDistance(word1, word2) {
  const n = word1.length, m = word2.length;
  const memo = new Int32Array((n + 1) * (m + 1)).fill(-1);
  function dist(i, j) {
    if (i === n) return m - j; // insert the rest of word2
    if (j === m) return n - i; // delete the rest of word1
    const key = i * (m + 1) + j;
    if (memo[key] !== -1) return memo[key];
    let best;
    if (word1[i] === word2[j]) {
      best = dist(i + 1, j + 1);
    } else {
      best = 1 + Math.min(dist(i + 1, j), dist(i, j + 1), dist(i + 1, j + 1));
    }
    memo[key] = best;
    return best;
  }
  return dist(0, 0);
}

2 · Bottom-up: fill the full (n+1) × (m+1) table

O(n·m) time · O(n·m) space

Bottom-up on prefixes: d[i][j] is the distance between the first i letters of word1 and the first j of word2. Row 0 holds j inserts and column 0 holds i deletes. A matching pair copies the diagonal; a mismatch takes one more than the smallest of the cell above, the cell to the left and the diagonal. Array.from with a mapping function gives each row its own array.

function minDistance(word1, word2) {
  const n = word1.length, m = word2.length;
  const d = Array.from({ length: n + 1 }, () => new Array(m + 1).fill(0));
  for (let i = 0; i <= n; i++) d[i][0] = i; // delete i letters
  for (let j = 0; j <= m; j++) d[0][j] = j; // insert j letters
  for (let i = 1; i <= n; i++) {
    for (let j = 1; j <= m; j++) {
      if (word1[i - 1] === word2[j - 1]) {
        d[i][j] = d[i - 1][j - 1];
      } else {
        d[i][j] = 1 + Math.min(d[i - 1][j], d[i][j - 1], d[i - 1][j - 1]);
      }
    }
  }
  return d[n][m];
}

3 · Two rows over the shorter word

O(n·m) time · O(min(n, m)) space

recommended

Each row reads only the row above, so two Uint16Array rows are enough; swap the references after each row instead of copying. The distance is symmetric, so the words are swapped first to run the rows over the shorter one, which makes the memory O(min(n, m)). Every cell of a row is written before it is read, so the reused row never needs clearing.

function minDistance(word1, word2) {
  if (word2.length > word1.length) [word1, word2] = [word2, word1];
  const m = word2.length;
  let prev = new Uint16Array(m + 1), cur = new Uint16Array(m + 1);
  for (let j = 0; j <= m; j++) prev[j] = j;
  for (let i = 1; i <= word1.length; i++) {
    cur[0] = i;
    for (let j = 1; j <= m; j++) {
      cur[j] = word1[i - 1] === word2[j - 1]
        ? prev[j - 1]
        : 1 + Math.min(prev[j], cur[j - 1], prev[j - 1]);
    }
    [prev, cur] = [cur, prev];
  }
  return prev[m];
}

3 reference approaches in TypeScript, from brute force to the one to reach for. Compare them with yours.

1 · Top-down: recurse on suffixes and cache each pair

O(n·m) time · O(n·m) space

dist(i, j) is the distance between the suffixes of the two words that start at i and j. An empty suffix costs the length of the other; equal first letters cost nothing; otherwise one move (delete, insert or replace) plus the cheapest of the three smaller problems. The cache is an Int32Array filled with -1, so each of the (n + 1) × (m + 1) pairs is solved once instead of exponentially often.

function minDistance(word1: string, word2: string): number {
  const n = word1.length, m = word2.length;
  const memo = new Int32Array((n + 1) * (m + 1)).fill(-1);
  const dist = (i: number, j: number): number => {
    if (i === n) return m - j; // insert the rest of word2
    if (j === m) return n - i; // delete the rest of word1
    const key = i * (m + 1) + j;
    if (memo[key] !== -1) return memo[key];
    const best = word1[i] === word2[j]
      ? dist(i + 1, j + 1)
      : 1 + Math.min(dist(i + 1, j), dist(i, j + 1), dist(i + 1, j + 1));
    memo[key] = best;
    return best;
  };
  return dist(0, 0);
}

2 · Bottom-up: fill the full (n+1) × (m+1) table

O(n·m) time · O(n·m) space

Bottom-up on prefixes with a number[][] table: d[i][j] is the distance between the first i letters of word1 and the first j of word2. The first row and column count inserts and deletes; every other cell copies the diagonal on a match, or adds one to the smallest of its three neighbours above, left and diagonally above-left.

function minDistance(word1: string, word2: string): number {
  const n = word1.length, m = word2.length;
  const d: number[][] = Array.from({ length: n + 1 }, () => new Array<number>(m + 1).fill(0));
  for (let i = 0; i <= n; i++) d[i][0] = i; // delete i letters
  for (let j = 0; j <= m; j++) d[0][j] = j; // insert j letters
  for (let i = 1; i <= n; i++) {
    for (let j = 1; j <= m; j++) {
      d[i][j] = word1[i - 1] === word2[j - 1]
        ? d[i - 1][j - 1]
        : 1 + Math.min(d[i - 1][j], d[i][j - 1], d[i - 1][j - 1]);
    }
  }
  return d[n][m];
}

3 · Two rows over the shorter word

O(n·m) time · O(min(n, m)) space

recommended

A row only reads the row above it, so keep prev and cur and swap them with a destructuring assignment after each row. Swapping the words first, so the rows run over the shorter one, brings the memory down to O(min(n, m)); the distance is the same in either direction.

function minDistance(word1: string, word2: string): number {
  const [a, b] = word1.length >= word2.length ? [word1, word2] : [word2, word1];
  const m = b.length;
  let prev = new Uint16Array(m + 1);
  let cur = new Uint16Array(m + 1);
  for (let j = 0; j <= m; j++) prev[j] = j;
  for (let i = 1; i <= a.length; i++) {
    cur[0] = i;
    for (let j = 1; j <= m; j++) {
      cur[j] = a[i - 1] === b[j - 1]
        ? prev[j - 1]
        : 1 + Math.min(prev[j], cur[j - 1], prev[j - 1]);
    }
    [prev, cur] = [cur, prev];
  }
  return prev[m];
}

3 reference approaches in Java, from brute force to the one to reach for. Compare them with yours.

1 · Top-down: recurse on suffixes and cache each pair

O(n·m) time · O(n·m) space

dist(i, j) solves the suffixes that start at i and j. An empty suffix costs the length of the other; equal letters cost nothing; otherwise one move plus the cheapest of delete, insert and replace. The cache is an int[][] filled with -1 through Arrays.fill on each row, so every pair is computed once. The words and the cache are passed down as parameters, which keeps the method static and free of shared fields between test cases.

import java.util.*;

public class Main {
    static int minDistance(String word1, String word2) {
        int[][] memo = new int[word1.length() + 1][word2.length() + 1];
        for (int[] row : memo) Arrays.fill(row, -1);
        return dist(word1, word2, 0, 0, memo);
    }

    static int dist(String a, String b, int i, int j, int[][] memo) {
        if (i == a.length()) return b.length() - j; // insert the rest of b
        if (j == b.length()) return a.length() - i; // delete the rest of a
        if (memo[i][j] != -1) return memo[i][j];
        int best;
        if (a.charAt(i) == b.charAt(j)) {
            best = dist(a, b, i + 1, j + 1, memo);
        } else {
            best = 1 + Math.min(dist(a, b, i + 1, j, memo),
                    Math.min(dist(a, b, i, j + 1, memo), dist(a, b, i + 1, j + 1, memo)));
        }
        memo[i][j] = best;
        return best;
    }
}

2 · Bottom-up: fill the full (n+1) × (m+1) table

O(n·m) time · O(n·m) space

Bottom-up on prefixes: d[i][j] is the distance between the first i letters of word1 and the first j of word2. Java zero-fills a new int[][], so only row 0 and column 0 need setting. A match copies the diagonal; a mismatch adds one to the smallest of the cells above, to the left and diagonally above-left. Math.min takes two arguments, so the three-way minimum nests two calls.

import java.util.*;

public class Main {
    static int minDistance(String word1, String word2) {
        int n = word1.length(), m = word2.length();
        int[][] d = new int[n + 1][m + 1];
        for (int i = 0; i <= n; i++) d[i][0] = i; // delete i letters
        for (int j = 0; j <= m; j++) d[0][j] = j; // insert j letters
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    d[i][j] = d[i - 1][j - 1];
                } else {
                    d[i][j] = 1 + Math.min(d[i - 1][j], Math.min(d[i][j - 1], d[i - 1][j - 1]));
                }
            }
        }
        return d[n][m];
    }
}

3 · Two rows over the shorter word

O(n·m) time · O(min(n, m)) space

recommended

Each row of the table reads only the previous one, so two int[] rows do the job. After a row is done, swap the two references; no copying. Swapping the words first so the rows span the shorter one gives O(min(n, m)) memory, and turning both words into char[] with toCharArray keeps the inner loop to plain array reads.

import java.util.*;

public class Main {
    static int minDistance(String word1, String word2) {
        if (word2.length() > word1.length()) {
            String t = word1; word1 = word2; word2 = t; // rows run over the shorter word
        }
        char[] a = word1.toCharArray(), b = word2.toCharArray();
        int m = b.length;
        int[] prev = new int[m + 1], cur = new int[m + 1];
        for (int j = 0; j <= m; j++) prev[j] = j;
        for (int i = 1; i <= a.length; i++) {
            cur[0] = i;
            for (int j = 1; j <= m; j++) {
                if (a[i - 1] == b[j - 1]) {
                    cur[j] = prev[j - 1];
                } else {
                    cur[j] = 1 + Math.min(prev[j], Math.min(cur[j - 1], prev[j - 1]));
                }
            }
            int[] t = prev; prev = cur; cur = t;
        }
        return prev[m];
    }
}

3 reference approaches in Go, from brute force to the one to reach for. Compare them with yours.

1 · Top-down: recurse on suffixes and cache each pair

O(n·m) time · O(n·m) space

dist(i, j) solves the suffixes that start at i and j. An empty suffix costs the length of the other; equal bytes cost nothing; otherwise one move plus the cheapest of delete, insert and replace. A closure that calls itself has to be declared first with var dist func(i, j int) int and assigned afterwards, because a := declaration is not in scope inside its own body. The cache is a slice of rows filled with -1.

package main

func minDistance(word1 string, word2 string) int {
	n, m := len(word1), len(word2)
	memo := make([][]int, n+1)
	for i := range memo {
		memo[i] = make([]int, m+1)
		for j := range memo[i] {
			memo[i][j] = -1
		}
	}
	var dist func(i, j int) int
	dist = func(i, j int) int {
		if i == n {
			return m - j // insert the rest of word2
		}
		if j == m {
			return n - i // delete the rest of word1
		}
		if memo[i][j] != -1 {
			return memo[i][j]
		}
		var best int
		if word1[i] == word2[j] {
			best = dist(i+1, j+1)
		} else {
			best = 1 + min(dist(i+1, j), dist(i, j+1), dist(i+1, j+1))
		}
		memo[i][j] = best
		return best
	}
	return dist(0, 0)
}

2 · Bottom-up: fill the full (n+1) × (m+1) table

O(n·m) time · O(n·m) space

Bottom-up on prefixes: d[i][j] is the distance between the first i bytes of word1 and the first j of word2. make zero-fills, so only row 0 and column 0 need values. A match copies the diagonal; a mismatch adds one to the smallest of the three neighbours, using the built-in variadic min that Go has had since 1.21.

package main

func minDistance(word1 string, word2 string) int {
	n, m := len(word1), len(word2)
	d := make([][]int, n+1)
	for i := range d {
		d[i] = make([]int, m+1)
		d[i][0] = i // delete i letters
	}
	for j := 0; j <= m; j++ {
		d[0][j] = j // insert j letters
	}
	for i := 1; i <= n; i++ {
		for j := 1; j <= m; j++ {
			if word1[i-1] == word2[j-1] {
				d[i][j] = d[i-1][j-1]
			} else {
				d[i][j] = 1 + min(d[i-1][j], d[i][j-1], d[i-1][j-1])
			}
		}
	}
	return d[n][m]
}

3 · Two rows over the shorter word

O(n·m) time · O(min(n, m)) space

recommended

Each row reads only the row above, so two slices are enough, swapped with prev, cur = cur, prev after every row. Swapping the words first so the rows span the shorter one gives O(min(n, m)) memory. Every cell of cur is written before it is read, so the reused slice never needs clearing.

package main

func minDistance(word1 string, word2 string) int {
	if len(word2) > len(word1) {
		word1, word2 = word2, word1 // rows run over the shorter word
	}
	m := len(word2)
	prev := make([]int, m+1)
	cur := make([]int, m+1)
	for j := range prev {
		prev[j] = j
	}
	for i := 1; i <= len(word1); i++ {
		cur[0] = i
		for j := 1; j <= m; j++ {
			if word1[i-1] == word2[j-1] {
				cur[j] = prev[j-1]
			} else {
				cur[j] = 1 + min(prev[j], cur[j-1], prev[j-1])
			}
		}
		prev, cur = cur, prev
	}
	return prev[m]
}

3 reference approaches in C#, from brute force to the one to reach for. Compare them with yours.

1 · Top-down: recurse on suffixes and cache each pair

O(n·m) time · O(n·m) space

Dist(i, j) solves the suffixes that start at i and j. An empty suffix costs the length of the other; equal letters cost nothing; otherwise one move plus the cheapest of delete, insert and replace. It is a local function, so it reads the words and the int[,] cache from the enclosing method without passing them along. The cache starts at -1, because 0 is a real distance.

using System;
using System.Collections.Generic;
using System.Linq;

public class Solution
{
    public static int MinDistance(string word1, string word2)
    {
        int n = word1.Length, m = word2.Length;
        var memo = new int[n + 1, m + 1];
        for (int i = 0; i <= n; i++)
            for (int j = 0; j <= m; j++)
                memo[i, j] = -1;

        int Dist(int i, int j)
        {
            if (i == n) return m - j; // insert the rest of word2
            if (j == m) return n - i; // delete the rest of word1
            if (memo[i, j] != -1) return memo[i, j];
            int best = word1[i] == word2[j]
                ? Dist(i + 1, j + 1)
                : 1 + Math.Min(Dist(i + 1, j), Math.Min(Dist(i, j + 1), Dist(i + 1, j + 1)));
            memo[i, j] = best;
            return best;
        }

        return Dist(0, 0);
    }
}

2 · Bottom-up: fill the full (n+1) × (m+1) table

O(n·m) time · O(n·m) space

Bottom-up on prefixes in a rectangular int[,]: d[i, j] is the distance between the first i letters of word1 and the first j of word2. Row 0 and column 0 count inserts and deletes. A match copies the diagonal; a mismatch adds one to the smallest of the cells above, to the left and diagonally above-left.

using System;
using System.Collections.Generic;
using System.Linq;

public class Solution
{
    public static int MinDistance(string word1, string word2)
    {
        int n = word1.Length, m = word2.Length;
        var d = new int[n + 1, m + 1];
        for (int i = 0; i <= n; i++) d[i, 0] = i; // delete i letters
        for (int j = 0; j <= m; j++) d[0, j] = j; // insert j letters
        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= m; j++)
            {
                d[i, j] = word1[i - 1] == word2[j - 1]
                    ? d[i - 1, j - 1]
                    : 1 + Math.Min(d[i - 1, j], Math.Min(d[i, j - 1], d[i - 1, j - 1]));
            }
        }
        return d[n, m];
    }
}

3 · Two rows over the shorter word

O(n·m) time · O(min(n, m)) space

recommended

Each row reads only the row above, so two int[] rows are enough. A tuple assignment, (prev, cur) = (cur, prev), swaps them after every row without copying. Swapping the words first so the rows span the shorter one gives O(min(n, m)) memory.

using System;
using System.Collections.Generic;
using System.Linq;

public class Solution
{
    public static int MinDistance(string word1, string word2)
    {
        if (word2.Length > word1.Length) (word1, word2) = (word2, word1); // rows over the shorter word
        int m = word2.Length;
        var prev = new int[m + 1];
        var cur = new int[m + 1];
        for (int j = 0; j <= m; j++) prev[j] = j;
        for (int i = 1; i <= word1.Length; i++)
        {
            cur[0] = i;
            for (int j = 1; j <= m; j++)
            {
                cur[j] = word1[i - 1] == word2[j - 1]
                    ? prev[j - 1]
                    : 1 + Math.Min(prev[j], Math.Min(cur[j - 1], prev[j - 1]));
            }
            (prev, cur) = (cur, prev);
        }
        return prev[m];
    }
}

3 reference approaches in C++, from brute force to the one to reach for. Compare them with yours.

1 · Top-down: recurse on suffixes and cache each pair

O(n·m) time · O(n·m) space

dist(i, j) solves the suffixes that start at i and j. An empty suffix costs the length of the other; equal letters cost nothing; otherwise one move plus the cheapest of delete, insert and replace. The helper takes the words and the vector<vector<int>> cache by const or plain reference, so nothing is copied per call. min with an initializer list takes three values at once.

#include <algorithm>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;

class Solution {
public:
    int minDistance(string word1, string word2) {
        vector<vector<int>> memo(word1.size() + 1, vector<int>(word2.size() + 1, -1));
        return dist(word1, word2, 0, 0, memo);
    }

private:
    int dist(const string& a, const string& b, int i, int j, vector<vector<int>>& memo) {
        int n = a.size(), m = b.size();
        if (i == n) return m - j; // insert the rest of b
        if (j == m) return n - i; // delete the rest of a
        int& slot = memo[i][j];
        if (slot != -1) return slot;
        if (a[i] == b[j]) {
            slot = dist(a, b, i + 1, j + 1, memo);
        } else {
            slot = 1 + min({dist(a, b, i + 1, j, memo), dist(a, b, i, j + 1, memo), dist(a, b, i + 1, j + 1, memo)});
        }
        return slot;
    }
};

2 · Bottom-up: fill the full (n+1) × (m+1) table

O(n·m) time · O(n·m) space

Bottom-up on prefixes: d[i][j] is the distance between the first i letters of word1 and the first j of word2. The vector constructor zero-fills the table, so only row 0 and column 0 need values. A match copies the diagonal; a mismatch adds one to the smallest of the cells above, to the left and diagonally above-left.

#include <algorithm>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;

class Solution {
public:
    int minDistance(string word1, string word2) {
        int n = word1.size(), m = word2.size();
        vector<vector<int>> d(n + 1, vector<int>(m + 1, 0));
        for (int i = 0; i <= n; i++) d[i][0] = i; // delete i letters
        for (int j = 0; j <= m; j++) d[0][j] = j; // insert j letters
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (word1[i - 1] == word2[j - 1]) {
                    d[i][j] = d[i - 1][j - 1];
                } else {
                    d[i][j] = 1 + min({d[i - 1][j], d[i][j - 1], d[i - 1][j - 1]});
                }
            }
        }
        return d[n][m];
    }
};

3 · Two rows over the shorter word

O(n·m) time · O(min(n, m)) space

recommended

Each row reads only the row above, so two vector<int> rows do the job. swap(prev, cur) exchanges their internal buffers in constant time, no element copying. Because the words arrive by value, swapping them first so the rows span the shorter one is cheap and gives O(min(n, m)) memory.

#include <algorithm>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;

class Solution {
public:
    int minDistance(string word1, string word2) {
        if (word2.size() > word1.size()) swap(word1, word2); // rows run over the shorter word
        int n = word1.size(), m = word2.size();
        vector<int> prev(m + 1), cur(m + 1);
        for (int j = 0; j <= m; j++) prev[j] = j;
        for (int i = 1; i <= n; i++) {
            cur[0] = i;
            for (int j = 1; j <= m; j++) {
                if (word1[i - 1] == word2[j - 1]) {
                    cur[j] = prev[j - 1];
                } else {
                    cur[j] = 1 + min({prev[j], cur[j - 1], prev[j - 1]});
                }
            }
            swap(prev, cur);
        }
        return prev[m];
    }
};

3 reference approaches in C, from brute force to the one to reach for. Compare them with yours.

1 · Top-down: recurse on suffixes and cache each pair

O(n·m) time · O(n·m) space

dist(i, j) solves the suffixes that start at word1 + i and word2 + j. An empty suffix costs the length of the other; equal letters cost nothing; otherwise one move plus the cheapest of delete, insert and replace. The cache is one flat malloc'ed block of (n + 1) × (m + 1) ints indexed as i * (m + 1) + j, set to -1 with memset (every byte 0xFF reads back as -1), and freed before returning.

#include <stdbool.h>
#include <stdlib.h>
#include <string.h>

static int min3(int a, int b, int c) {
    int m = a < b ? a : b;
    return m < c ? m : c;
}

static int dist(const char* a, int n, const char* b, int m, int i, int j, int* memo) {
    if (i == n) return m - j; // insert the rest of b
    if (j == m) return n - i; // delete the rest of a
    int* slot = &memo[i * (m + 1) + j];
    if (*slot != -1) return *slot;
    if (a[i] == b[j]) {
        *slot = dist(a, n, b, m, i + 1, j + 1, memo);
    } else {
        *slot = 1 + min3(dist(a, n, b, m, i + 1, j, memo),
                         dist(a, n, b, m, i, j + 1, memo),
                         dist(a, n, b, m, i + 1, j + 1, memo));
    }
    return *slot;
}

int minDistance(char* word1, char* word2) {
    int n = (int)strlen(word1), m = (int)strlen(word2);
    size_t cells = (size_t)(n + 1) * (size_t)(m + 1);
    int* memo = malloc(cells * sizeof *memo);
    memset(memo, -1, cells * sizeof *memo); // all bytes 0xFF = -1 in every int
    int result = dist(word1, n, word2, m, 0, 0, memo);
    free(memo);
    return result;
}

2 · Bottom-up: fill the full (n+1) × (m+1) table

O(n·m) time · O(n·m) space

Bottom-up on prefixes: d[i][j] is the distance between the first i letters of word1 and the first j of word2. The table is a C99 variable-length array, int d[n + 1][m + 1], about 362 KB on the stack at the size bound, so there is nothing to free. Row 0 counts inserts, column 0 counts deletes, a match copies the diagonal and a mismatch adds one to the smallest of the cells above, left and above-left.

#include <stdbool.h>
#include <stdlib.h>
#include <string.h>

static int min3(int a, int b, int c) {
    int m = a < b ? a : b;
    return m < c ? m : c;
}

int minDistance(char* word1, char* word2) {
    int n = (int)strlen(word1), m = (int)strlen(word2);
    int d[n + 1][m + 1]; // a VLA: 301 x 301 ints at most
    for (int i = 0; i <= n; i++) d[i][0] = i; // delete i letters
    for (int j = 0; j <= m; j++) d[0][j] = j; // insert j letters
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (word1[i - 1] == word2[j - 1]) {
                d[i][j] = d[i - 1][j - 1];
            } else {
                d[i][j] = 1 + min3(d[i - 1][j], d[i][j - 1], d[i - 1][j - 1]);
            }
        }
    }
    return d[n][m];
}

3 · Two rows over the shorter word

O(n·m) time · O(min(n, m)) space

recommended

Each row reads only the row above, so keep two malloc'ed rows and swap the two pointers after every row; nothing is copied. Swapping the two char* first makes the rows as long as the shorter word, so the memory is O(min(n, m)). Both rows are freed after the answer is read from prev[m].

#include <stdbool.h>
#include <stdlib.h>
#include <string.h>

static int min3(int a, int b, int c) {
    int m = a < b ? a : b;
    return m < c ? m : c;
}

int minDistance(char* word1, char* word2) {
    if (strlen(word2) > strlen(word1)) {
        char* t = word1; word1 = word2; word2 = t; // rows run over the shorter word
    }
    int n = (int)strlen(word1), m = (int)strlen(word2);
    int* prev = malloc((size_t)(m + 1) * sizeof *prev);
    int* cur = malloc((size_t)(m + 1) * sizeof *cur);
    for (int j = 0; j <= m; j++) prev[j] = j;
    for (int i = 1; i <= n; i++) {
        cur[0] = i;
        for (int j = 1; j <= m; j++) {
            if (word1[i - 1] == word2[j - 1]) {
                cur[j] = prev[j - 1];
            } else {
                cur[j] = 1 + min3(prev[j], cur[j - 1], prev[j - 1]);
            }
        }
        int* t = prev; prev = cur; cur = t;
    }
    int result = prev[m];
    free(prev);
    free(cur);
    return result;
}

3 reference approaches in Kotlin, from brute force to the one to reach for. Compare them with yours.

1 · Top-down: recurse on suffixes and cache each pair

O(n·m) time · O(n·m) space

dist(i, j) solves the suffixes that start at i and j. An empty suffix costs the length of the other; equal letters cost nothing; otherwise one move plus minOf of delete, insert and replace. The cache is an Array<IntArray> built with IntArray(m + 1) { -1 }, and dist is a local function, so it sees the words and the cache without passing them.

class Solution {
    fun minDistance(word1: String, word2: String): Int {
        val n = word1.length
        val m = word2.length
        val memo = Array(n + 1) { IntArray(m + 1) { -1 } }

        fun dist(i: Int, j: Int): Int {
            if (i == n) return m - j // insert the rest of word2
            if (j == m) return n - i // delete the rest of word1
            if (memo[i][j] != -1) return memo[i][j]
            val best = if (word1[i] == word2[j]) {
                dist(i + 1, j + 1)
            } else {
                1 + minOf(dist(i + 1, j), dist(i, j + 1), dist(i + 1, j + 1))
            }
            memo[i][j] = best
            return best
        }

        return dist(0, 0)
    }
}

2 · Bottom-up: fill the full (n+1) × (m+1) table

O(n·m) time · O(n·m) space

Bottom-up on prefixes: d[i][j] is the distance between the first i letters of word1 and the first j of word2. The Array and IntArray constructors take the index, so row 0 and column 0 are filled while the table is built. A match copies the diagonal; a mismatch adds one to the smallest of the cells above, left and above-left. 1..n is simply empty when a word is.

class Solution {
    fun minDistance(word1: String, word2: String): Int {
        val n = word1.length
        val m = word2.length
        val d = Array(n + 1) { i -> IntArray(m + 1) { j -> if (i == 0) j else if (j == 0) i else 0 } }
        for (i in 1..n) {
            for (j in 1..m) {
                d[i][j] = if (word1[i - 1] == word2[j - 1]) {
                    d[i - 1][j - 1]
                } else {
                    1 + minOf(d[i - 1][j], d[i][j - 1], d[i - 1][j - 1])
                }
            }
        }
        return d[n][m]
    }
}

3 · Two rows over the shorter word

O(n·m) time · O(min(n, m)) space

recommended

Each row reads only the row above, so two IntArray rows are enough. A destructured Pair puts the longer word first, which makes the rows as long as the shorter one, and prev = cur.also { cur = prev } swaps the two references after each row with no copy. Memory is O(min(n, m)).

class Solution {
    fun minDistance(word1: String, word2: String): Int {
        // rows run over the shorter word
        val (a, b) = if (word1.length >= word2.length) word1 to word2 else word2 to word1
        val m = b.length
        var prev = IntArray(m + 1) { it }
        var cur = IntArray(m + 1)
        for (i in 1..a.length) {
            cur[0] = i
            for (j in 1..m) {
                cur[j] = if (a[i - 1] == b[j - 1]) prev[j - 1] else 1 + minOf(prev[j], cur[j - 1], prev[j - 1])
            }
            prev = cur.also { cur = prev }
        }
        return prev[m]
    }
}

3 reference approaches in Rust, from brute force to the one to reach for. Compare them with yours.

1 · Top-down: recurse on suffixes and cache each pair

O(n·m) time · O(n·m) space

dist(i, j) solves the suffixes that start at i and j. An empty suffix costs the length of the other; equal bytes cost nothing; otherwise one move plus the cheapest of delete, insert and replace. The words go in as &[u8] from as_bytes, and the cache is a Vec<Vec<i32>> of -1 passed down as &mut, so the helper is an associated function with no shared state.

impl Solution {
    pub fn min_distance(word1: String, word2: String) -> i32 {
        let (a, b) = (word1.as_bytes(), word2.as_bytes());
        let mut memo = vec![vec![-1; b.len() + 1]; a.len() + 1];
        Self::dist(a, b, 0, 0, &mut memo)
    }

    fn dist(a: &[u8], b: &[u8], i: usize, j: usize, memo: &mut Vec<Vec<i32>>) -> i32 {
        if i == a.len() {
            return (b.len() - j) as i32; // insert the rest of b
        }
        if j == b.len() {
            return (a.len() - i) as i32; // delete the rest of a
        }
        if memo[i][j] != -1 {
            return memo[i][j];
        }
        let best = if a[i] == b[j] {
            Self::dist(a, b, i + 1, j + 1, memo)
        } else {
            let delete = Self::dist(a, b, i + 1, j, memo);
            let insert = Self::dist(a, b, i, j + 1, memo);
            let replace = Self::dist(a, b, i + 1, j + 1, memo);
            1 + delete.min(insert).min(replace)
        };
        memo[i][j] = best;
        best
    }
}

2 · Bottom-up: fill the full (n+1) × (m+1) table

O(n·m) time · O(n·m) space

Bottom-up on prefixes: d[i][j] is the distance between the first i bytes of word1 and the first j of word2. The table holds usize so the indices go in without casts, and only the final answer becomes i32. Row 0 counts inserts, column 0 counts deletes, a match copies the diagonal and a mismatch adds one to the smallest of the three neighbours, chained with .min().

impl Solution {
    pub fn min_distance(word1: String, word2: String) -> i32 {
        let (a, b) = (word1.as_bytes(), word2.as_bytes());
        let (n, m) = (a.len(), b.len());
        let mut d = vec![vec![0usize; m + 1]; n + 1];
        for (i, row) in d.iter_mut().enumerate() {
            row[0] = i; // delete i letters
        }
        for j in 0..=m {
            d[0][j] = j; // insert j letters
        }
        for i in 1..=n {
            for j in 1..=m {
                d[i][j] = if a[i - 1] == b[j - 1] {
                    d[i - 1][j - 1]
                } else {
                    1 + d[i - 1][j].min(d[i][j - 1]).min(d[i - 1][j - 1])
                };
            }
        }
        d[n][m] as i32
    }
}

3 · Two rows over the shorter word

O(n·m) time · O(min(n, m)) space

recommended

Each row reads only the row above, so keep two Vec<usize> rows and std::mem::swap them after every row: that swaps the buffers, it copies nothing. Swapping the two byte slices first makes the rows as long as the shorter word, for O(min(n, m)) memory. Iterating with enumerate over the bytes skips the bounds checks on the words.

impl Solution {
    pub fn min_distance(word1: String, word2: String) -> i32 {
        let (mut a, mut b) = (word1.as_bytes(), word2.as_bytes());
        if b.len() > a.len() {
            std::mem::swap(&mut a, &mut b); // rows run over the shorter word
        }
        let m = b.len();
        let mut prev: Vec<usize> = (0..=m).collect();
        let mut cur = vec![0usize; m + 1];
        for (i, &x) in a.iter().enumerate() {
            cur[0] = i + 1;
            for (j, &y) in b.iter().enumerate() {
                cur[j + 1] = if x == y {
                    prev[j]
                } else {
                    1 + prev[j + 1].min(cur[j]).min(prev[j])
                };
            }
            std::mem::swap(&mut prev, &mut cur);
        }
        prev[m] as i32
    }
}

3 reference approaches in Swift, from brute force to the one to reach for. Compare them with yours.

1 · Top-down: recurse on suffixes and cache each pair

O(n·m) time · O(n·m) space

dist(i, j) solves the suffixes that start at i and j. An empty suffix costs the length of the other; equal letters cost nothing; otherwise one move plus the cheapest of delete, insert and replace, using the variadic min(_:_:_:). The words become [UInt8] through Array(word.utf8) so they index by Int, and the nested function captures the -1-filled [[Int]] cache and writes into it directly.

class Solution {
    func minDistance(_ word1: String, _ word2: String) -> Int {
        let a = Array(word1.utf8), b = Array(word2.utf8)
        var memo = [[Int]](repeating: [Int](repeating: -1, count: b.count + 1), count: a.count + 1)

        func dist(_ i: Int, _ j: Int) -> Int {
            if i == a.count { return b.count - j } // insert the rest of b
            if j == b.count { return a.count - i } // delete the rest of a
            if memo[i][j] != -1 { return memo[i][j] }
            let best: Int
            if a[i] == b[j] {
                best = dist(i + 1, j + 1)
            } else {
                best = 1 + min(dist(i + 1, j), dist(i, j + 1), dist(i + 1, j + 1))
            }
            memo[i][j] = best
            return best
        }

        return dist(0, 0)
    }
}

2 · Bottom-up: fill the full (n+1) × (m+1) table

O(n·m) time · O(n·m) space

Bottom-up on prefixes: d[i][j] is the distance between the first i letters of word1 and the first j of word2. Row 0 counts inserts and column 0 counts deletes. The loops go over enumerated() and write cell [i + 1][j + 1], which sidesteps 1...n, a range that traps when a word is empty. A match copies the diagonal; a mismatch adds one to the smallest of the three neighbours.

class Solution {
    func minDistance(_ word1: String, _ word2: String) -> Int {
        let a = Array(word1.utf8), b = Array(word2.utf8)
        let n = a.count, m = b.count
        var d = [[Int]](repeating: [Int](repeating: 0, count: m + 1), count: n + 1)
        for i in 0...n { d[i][0] = i } // delete i letters
        for j in 0...m { d[0][j] = j } // insert j letters
        for (i, x) in a.enumerated() {
            for (j, y) in b.enumerated() {
                if x == y {
                    d[i + 1][j + 1] = d[i][j]
                } else {
                    d[i + 1][j + 1] = 1 + min(d[i][j + 1], d[i + 1][j], d[i][j])
                }
            }
        }
        return d[n][m]
    }
}

3 · Two rows over the shorter word

O(n·m) time · O(min(n, m)) space

recommended

Each row reads only the row above, so keep two [Int] rows and swap(&prev, &cur) after every row. Swift arrays are values, but the swap only exchanges the two buffers, with no copy. Swapping the byte arrays first makes the rows as long as the shorter word, for O(min(n, m)) memory.

class Solution {
    func minDistance(_ word1: String, _ word2: String) -> Int {
        var a = Array(word1.utf8), b = Array(word2.utf8)
        if b.count > a.count { swap(&a, &b) } // rows run over the shorter word
        let m = b.count
        var prev = Array(0...m)
        var cur = [Int](repeating: 0, count: m + 1)
        for (i, x) in a.enumerated() {
            cur[0] = i + 1
            for (j, y) in b.enumerated() {
                cur[j + 1] = x == y ? prev[j] : 1 + min(prev[j + 1], cur[j], prev[j])
            }
            swap(&prev, &cur)
        }
        return prev[m]
    }
}

3 reference approaches in PHP, from brute force to the one to reach for. Compare them with yours.

1 · Top-down: recurse on suffixes and cache each pair

O(n·m) time · O(n·m) space

dist($i, $j) solves the suffixes that start at $i and $j. An empty suffix costs the length of the other; equal letters cost nothing; otherwise one move plus the cheapest of delete, insert and replace, using the variadic min(). The cache is a nested array_fill of -1 passed as array &$memo: without the &, PHP would copy the array on the first write in every call and the answers would never be kept.

<?php

class Solution {
    /**
     * @param string $word1
     * @param string $word2
     * @return int
     */
    function minDistance(string $word1, string $word2): int {
        $memo = array_fill(0, strlen($word1) + 1, array_fill(0, strlen($word2) + 1, -1));
        return $this->dist($word1, $word2, 0, 0, $memo);
    }

    private function dist(string $a, string $b, int $i, int $j, array &$memo): int {
        $n = strlen($a);
        $m = strlen($b);
        if ($i === $n) {
            return $m - $j; // insert the rest of $b
        }
        if ($j === $m) {
            return $n - $i; // delete the rest of $a
        }
        if ($memo[$i][$j] !== -1) {
            return $memo[$i][$j];
        }
        if ($a[$i] === $b[$j]) {
            $best = $this->dist($a, $b, $i + 1, $j + 1, $memo);
        } else {
            $best = 1 + min(
                $this->dist($a, $b, $i + 1, $j, $memo),
                $this->dist($a, $b, $i, $j + 1, $memo),
                $this->dist($a, $b, $i + 1, $j + 1, $memo),
            );
        }
        return $memo[$i][$j] = $best;
    }
}

2 · Bottom-up: fill the full (n+1) × (m+1) table

O(n·m) time · O(n·m) space

Bottom-up on prefixes: $d[$i][$j] is the distance between the first $i letters of $word1 and the first $j of $word2. Row 0 counts inserts and column 0 counts deletes. A match copies the diagonal; a mismatch adds one to the smallest of the cells above, left and above-left. Strings index by byte with $word1[$i - 1], which is exact for lowercase ASCII.

<?php

class Solution {
    /**
     * @param string $word1
     * @param string $word2
     * @return int
     */
    function minDistance(string $word1, string $word2): int {
        $n = strlen($word1);
        $m = strlen($word2);
        $d = array_fill(0, $n + 1, array_fill(0, $m + 1, 0));
        for ($i = 0; $i <= $n; $i++) {
            $d[$i][0] = $i; // delete $i letters
        }
        for ($j = 0; $j <= $m; $j++) {
            $d[0][$j] = $j; // insert $j letters
        }
        for ($i = 1; $i <= $n; $i++) {
            for ($j = 1; $j <= $m; $j++) {
                if ($word1[$i - 1] === $word2[$j - 1]) {
                    $d[$i][$j] = $d[$i - 1][$j - 1];
                } else {
                    $d[$i][$j] = 1 + min($d[$i - 1][$j], $d[$i][$j - 1], $d[$i - 1][$j - 1]);
                }
            }
        }
        return $d[$n][$m];
    }
}

3 · Two rows over the shorter word

O(n·m) time · O(min(n, m)) space

recommended

Each row reads only the row above, so two arrays are enough. Array destructuring swaps the words so the rows run over the shorter one, and swaps the rows after each pass: [$prev, $cur] = [$cur, $prev]. PHP arrays are copy-on-write, so this swap moves no data. Memory is O(min(n, m)).

<?php

class Solution {
    /**
     * @param string $word1
     * @param string $word2
     * @return int
     */
    function minDistance(string $word1, string $word2): int {
        if (strlen($word2) > strlen($word1)) {
            [$word1, $word2] = [$word2, $word1]; // rows run over the shorter word
        }
        $n = strlen($word1);
        $m = strlen($word2);
        $prev = range(0, $m);
        $cur = array_fill(0, $m + 1, 0);
        for ($i = 1; $i <= $n; $i++) {
            $cur[0] = $i;
            $a = $word1[$i - 1];
            for ($j = 1; $j <= $m; $j++) {
                if ($a === $word2[$j - 1]) {
                    $cur[$j] = $prev[$j - 1];
                } else {
                    $cur[$j] = 1 + min($prev[$j], $cur[$j - 1], $prev[$j - 1]);
                }
            }
            [$prev, $cur] = [$cur, $prev];
        }
        return $prev[$m];
    }
}

3 reference approaches in Ruby, from brute force to the one to reach for. Compare them with yours.

1 · Top-down: recurse on suffixes and cache each pair

O(n·m) time · O(n·m) space

suffix_distance(a, b, i, j, memo) solves the suffixes that start at i and j. An empty suffix costs the length of the other; equal letters cost nothing; otherwise one move plus the cheapest of delete, insert and replace. The cache is Array.new(n + 1) { Array.new(m + 1, -1) }, and the assignment memo[i][j] = … is the method's last expression, so it stores and returns the answer in one step.

# @param {String} word1
# @param {String} word2
# @return {Integer}
def min_distance(word1, word2)
  memo = Array.new(word1.size + 1) { Array.new(word2.size + 1, -1) }
  suffix_distance(word1, word2, 0, 0, memo)
end

def suffix_distance(a, b, i, j, memo)
  return b.size - j if i == a.size # insert the rest of b
  return a.size - i if j == b.size # delete the rest of a
  return memo[i][j] unless memo[i][j] == -1

  memo[i][j] =
    if a[i] == b[j]
      suffix_distance(a, b, i + 1, j + 1, memo)
    else
      1 + [
        suffix_distance(a, b, i + 1, j, memo),
        suffix_distance(a, b, i, j + 1, memo),
        suffix_distance(a, b, i + 1, j + 1, memo)
      ].min
    end
end

2 · Bottom-up: fill the full (n+1) × (m+1) table

O(n·m) time · O(n·m) space

Bottom-up on prefixes: d[i][j] is the distance between the first i letters of word1 and the first j of word2. Each row starts as [i] + [0] * m, and row 0 is replaced by (0..m).to_a. A match copies the diagonal; a mismatch adds one to the smallest of the cells above, left and above-left. 1..n is simply empty when a word is.

# @param {String} word1
# @param {String} word2
# @return {Integer}
def min_distance(word1, word2)
  n = word1.size
  m = word2.size
  d = Array.new(n + 1) { |i| [i] + [0] * m } # column 0: delete i letters
  d[0] = (0..m).to_a # row 0: insert j letters
  (1..n).each do |i|
    (1..m).each do |j|
      d[i][j] =
        if word1[i - 1] == word2[j - 1]
          d[i - 1][j - 1]
        else
          1 + [d[i - 1][j], d[i][j - 1], d[i - 1][j - 1]].min
        end
    end
  end
  d[n][m]
end

3 · Two rows over the shorter word

O(n·m) time · O(min(n, m)) space

recommended

Each row reads only the row above, so keep two arrays and swap them with parallel assignment after every row. Swapping the words first makes the rows as long as the shorter one, for O(min(n, m)) memory. The words become integer arrays with bytes, so the inner loop compares Integers instead of building a new one-letter String for every word[i].

# @param {String} word1
# @param {String} word2
# @return {Integer}
def min_distance(word1, word2)
  word1, word2 = word2, word1 if word2.size > word1.size # rows run over the shorter word
  b = word2.bytes
  m = b.size
  prev = (0..m).to_a
  cur = Array.new(m + 1, 0)
  word1.each_byte.with_index(1) do |x, i|
    cur[0] = i
    b.each_with_index do |y, j|
      cur[j + 1] = x == y ? prev[j] : 1 + [prev[j + 1], cur[j], prev[j]].min
    end
    prev, cur = cur, prev
  end
  prev[m]
end

3 reference approaches in Dart, from brute force to the one to reach for. Compare them with yours.

1 · Top-down: recurse on suffixes and cache each pair

O(n·m) time · O(n·m) space

dist(i, j) solves the suffixes that start at i and j. An empty suffix costs the length of the other; equal letters cost nothing; otherwise one move plus the cheapest of delete, insert and replace. Letters are compared with codeUnitAt, which returns an int instead of a new one-letter String. The cache is one List.filled(m + 1, -1) per row, built with List.generate so the rows are separate lists.

import 'dart:math';

class Solution {
  int minDistance(String word1, String word2) {
    final n = word1.length, m = word2.length;
    final memo = List.generate(n + 1, (_) => List.filled(m + 1, -1));

    int dist(int i, int j) {
      if (i == n) return m - j; // insert the rest of word2
      if (j == m) return n - i; // delete the rest of word1
      if (memo[i][j] != -1) return memo[i][j];
      final int best = word1.codeUnitAt(i) == word2.codeUnitAt(j)
          ? dist(i + 1, j + 1)
          : 1 + min(dist(i + 1, j), min(dist(i, j + 1), dist(i + 1, j + 1)));
      memo[i][j] = best;
      return best;
    }

    return dist(0, 0);
  }
}

2 · Bottom-up: fill the full (n+1) × (m+1) table

O(n·m) time · O(n·m) space

Bottom-up on prefixes: d[i][j] is the distance between the first i letters of word1 and the first j of word2. Nested List.generate calls build the table with row 0 and column 0 already set. A match copies the diagonal; a mismatch adds one to the smallest of the cells above, left and above-left, using min from dart:math.

import 'dart:math';

class Solution {
  int minDistance(String word1, String word2) {
    final n = word1.length, m = word2.length;
    final d = List.generate(n + 1, (i) => List.generate(m + 1, (j) => i == 0 ? j : (j == 0 ? i : 0)));
    for (var i = 1; i <= n; i++) {
      for (var j = 1; j <= m; j++) {
        if (word1.codeUnitAt(i - 1) == word2.codeUnitAt(j - 1)) {
          d[i][j] = d[i - 1][j - 1];
        } else {
          d[i][j] = 1 + min(d[i - 1][j], min(d[i][j - 1], d[i - 1][j - 1]));
        }
      }
    }
    return d[n][m];
  }
}

3 · Two rows over the shorter word

O(n·m) time · O(min(n, m)) space

recommended

Each row reads only the row above, so two List<int> rows are enough, swapped by reference after each row. Swapping the words first makes the rows as long as the shorter one, for O(min(n, m)) memory, and reading codeUnits into lists up front keeps the inner loop to plain index reads.

import 'dart:math';

class Solution {
  int minDistance(String word1, String word2) {
    if (word2.length > word1.length) {
      final t = word1; word1 = word2; word2 = t; // rows run over the shorter word
    }
    final a = word1.codeUnits, b = word2.codeUnits;
    final m = b.length;
    var prev = List<int>.generate(m + 1, (j) => j);
    var cur = List<int>.filled(m + 1, 0);
    for (var i = 1; i <= a.length; i++) {
      cur[0] = i;
      for (var j = 1; j <= m; j++) {
        cur[j] = a[i - 1] == b[j - 1] ? prev[j - 1] : 1 + min(prev[j], min(cur[j - 1], prev[j - 1]));
      }
      final t = prev; prev = cur; cur = t;
    }
    return prev[m];
  }
}

3 reference approaches in Scala, from brute force to the one to reach for. Compare them with yours.

1 · Top-down: recurse on suffixes and cache each pair

O(n·m) time · O(n·m) space

dist(i, j) solves the suffixes that start at i and j. It is one if/else expression: an empty suffix costs the length of the other, a cached pair returns its value, equal letters cost nothing, and otherwise one move plus the cheapest of delete, insert and replace. The cache is Array.fill(n + 1, m + 1)(-1), and since nothing returns early there is no return anywhere.

object Solution {
  def minDistance(word1: String, word2: String): Int = {
    val n = word1.length
    val m = word2.length
    val memo = Array.fill(n + 1, m + 1)(-1)

    def dist(i: Int, j: Int): Int =
      if (i == n) m - j // insert the rest of word2
      else if (j == m) n - i // delete the rest of word1
      else if (memo(i)(j) != -1) memo(i)(j)
      else {
        val best =
          if (word1(i) == word2(j)) dist(i + 1, j + 1)
          else 1 + (dist(i + 1, j) min dist(i, j + 1) min dist(i + 1, j + 1))
        memo(i)(j) = best
        best
      }

    dist(0, 0)
  }
}

2 · Bottom-up: fill the full (n+1) × (m+1) table

O(n·m) time · O(n·m) space

Bottom-up on prefixes: d(i)(j) is the distance between the first i letters of word1 and the first j of word2. Array.tabulate builds the table with row 0 and column 0 already set, and a for over two ranges fills the rest: a match copies the diagonal, a mismatch adds one to the smallest of the three neighbours. The loop never returns early, so a for is safe here.

object Solution {
  def minDistance(word1: String, word2: String): Int = {
    val n = word1.length
    val m = word2.length
    val d = Array.tabulate(n + 1, m + 1)((i, j) => if (i == 0) j else if (j == 0) i else 0)
    for (i <- 1 to n; j <- 1 to m) {
      d(i)(j) =
        if (word1(i - 1) == word2(j - 1)) d(i - 1)(j - 1)
        else 1 + (d(i - 1)(j) min d(i)(j - 1) min d(i - 1)(j - 1))
    }
    d(n)(m)
  }
}

3 · Two rows over the shorter word

O(n·m) time · O(min(n, m)) space

recommended

Each row reads only the row above, so keep two Array[Int] rows in vars and swap them after every row. A tuple puts the longer word first, which makes the rows as long as the shorter one, for O(min(n, m)) memory. Plain while loops keep the inner loop free of range and closure overhead.

object Solution {
  def minDistance(word1: String, word2: String): Int = {
    // rows run over the shorter word
    val (a, b) = if (word1.length >= word2.length) (word1, word2) else (word2, word1)
    val m = b.length
    var prev = Array.tabulate(m + 1)(j => j)
    var cur = new Array[Int](m + 1)
    var i = 1
    while (i <= a.length) {
      cur(0) = i
      var j = 1
      while (j <= m) {
        cur(j) =
          if (a(i - 1) == b(j - 1)) prev(j - 1)
          else 1 + (prev(j) min cur(j - 1) min prev(j - 1))
        j += 1
      }
      val t = prev; prev = cur; cur = t
      i += 1
    }
    prev(m)
  }
}

FAQ for Ruby

Why not Array.new(n + 1, Array.new(m + 1, -1))?

With a second argument, Array.new puts the same object in every slot, so every row would be one shared array and writing memo[2][3] would change all of them. The block form Array.new(n + 1) { Array.new(m + 1, -1) } runs the block once per row and gives each row its own array.

Can I memoise with a Hash instead?

Yes: memo = Hash.new and memo[[i, j]] ||= ... is a common Ruby idiom, and a Hash.new { |h, (i, j)| h[[i, j]] = ... } default block can even hold the whole recursion. Each key is a new two-element array that must be hashed, though, so the nested Array with -1 is faster and uses less memory.

Will the recursion hit SystemStackError?

The deepest chain is n + m calls, 600 frames at the size bound, which the default Ruby VM stack handles easily. Ruby stacks are smaller than JVM ones, so for words in the thousands use the table or the two-row loop.

Is there a built-in Levenshtein in Ruby?

Not in core. DidYouMean::Levenshtein.distance(a, b) ships with Ruby for the did-you-mean suggestions and returns this number, and gems such as levenshtein-ffi or damerau-levenshtein are faster. On a practice problem you write the loop yourself.

Why use bytes in the two-row version?

word[i] returns a new one-character String each time, so the inner loop allocates on every comparison. bytes turns the word into an Array of Integers once, and comparing two Integers allocates nothing. For lowercase ASCII each letter is exactly one byte; for Unicode use chars instead.

Keep going

Largest Rectangle in Histogram40 / 40 · Monotonic stack · Hard

Try Edit Distance in Python (Edit Distance in Python), JavaScript (Edit Distance in JavaScript), TypeScript (Edit Distance in TypeScript), Java (Edit Distance in Java), Go (Edit Distance in Go), C# (Edit Distance in C#), C++ (Edit Distance in C++), C (Edit Distance in C), Kotlin (Edit Distance in Kotlin), Rust (Edit Distance in Rust), Swift (Edit Distance in Swift), PHP (Edit Distance in PHP), Dart (Edit Distance in Dart) or Scala (Edit Distance in Scala) instead.

min_distance.rb

Ruby 4.0

Not run yet

+ 8 hidden

Input

word1 = "lantern"
word2 = "pattern"

Expected

Replace the l with p and the first n with t; the a and the ending tern already match.