Edit Distance (Levenshtein) With Dynamic Programming, Explained

The problem

Turn horse into ros with the fewest single-character edits: insert, delete or replace a character. One answer: replace h with r (rorse), delete r (rose), delete e (ros): three edits. Spell checkers, DNA alignment and fuzzy search all compute this.

State and recurrence

Let D(i, j) be the fewest edits turning the prefix a[:i] into b[:j]. Look at the last characters:

Recurrence

D(i, j)

if a[i − 1] = b[j − 1]: D(i − 1, j − 1), free;
otherwise 1 + min of: D(i − 1, j) (delete a[i − 1]), D(i, j − 1) (insert b[j − 1]), D(i − 1, j − 1) (replace).

base cases

D(i, 0) = i (delete everything), D(0, j) = j (insert everything).

Forgetting the free match, and always paying 1, is the classic bug. It fails the coverage check: the solution that keeps matching characters has no path.

Bottom-up

D(i, j) for horse (rows) and ros (columns).

Step 1 / 16

Base cases filled first.
Step 2 / 16

'h' ≠ 'r': 1 + min(delete 1, insert 1, replace 0) = 1.
Step 3 / 16

'h' ≠ 'o': 1 + min(delete 2, insert 1, replace 1) = 2.
Step 4 / 16

'h' ≠ 's': 1 + min(delete 3, insert 2, replace 2) = 3.
Step 5 / 16

'o' ≠ 'r': 1 + min(delete 1, insert 2, replace 1) = 2.
Step 6 / 16

'o' = 'o': keep it for free, 1.
Step 7 / 16

'o' ≠ 's': 1 + min(delete 3, insert 1, replace 2) = 2.
Step 8 / 16

'r' = 'r': keep it for free, 2.
Step 9 / 16

'r' ≠ 'o': 1 + min(delete 1, insert 2, replace 2) = 2.
Step 10 / 16

'r' ≠ 's': 1 + min(delete 2, insert 2, replace 1) = 2.
Step 11 / 16

's' ≠ 'r': 1 + min(delete 2, insert 4, replace 3) = 3.
Step 12 / 16

's' ≠ 'o': 1 + min(delete 2, insert 3, replace 2) = 3.
Step 13 / 16

's' = 's': keep it for free, 2.
Step 14 / 16

'e' ≠ 'r': 1 + min(delete 3, insert 5, replace 4) = 4.
Step 15 / 16

'e' ≠ 'o': 1 + min(delete 3, insert 4, replace 3) = 4.
Step 16 / 16

'e' ≠ 's': 1 + min(delete 2, insert 4, replace 3) = 3. D(5, 3) = 3: three edits.

Code and cost

def edit_distance(a, b):
    prev = list(range(len(b) + 1))             # row i = 0
    for i in range(1, len(a) + 1):
        cur = [i] + [0] * len(b)
        for j in range(1, len(b) + 1):
            if a[i - 1] == b[j - 1]:
                cur[j] = prev[j - 1]           # match: free
            else:
                cur[j] = 1 + min(prev[j], cur[j - 1], prev[j - 1])
        prev = cur
    return prev[len(b)]

int edit_distance(const std::string& a, const std::string& b) {
    std::vector<int> prev(b.size() + 1), cur(b.size() + 1);
    std::iota(prev.begin(), prev.end(), 0);                 // row i = 0
    for (size_t i = 1; i <= a.size(); ++i) {
        cur[0] = i;
        for (size_t j = 1; j <= b.size(); ++j)
            cur[j] = a[i - 1] == b[j - 1] ? prev[j - 1]     // match: free
                   : 1 + std::min({prev[j], cur[j - 1], prev[j - 1]});
        std::swap(prev, cur);
    }
    return prev[b.size()];
}

static int editDistance(String a, String b) {
    int[] prev = new int[b.length() + 1], cur = new int[b.length() + 1];
    for (int j = 0; j <= b.length(); j++) prev[j] = j;      // row i = 0
    for (int i = 1; i <= a.length(); i++) {
        cur[0] = i;
        for (int j = 1; j <= b.length(); j++)
            cur[j] = a.charAt(i - 1) == b.charAt(j - 1) ? prev[j - 1]   // match: free
                   : 1 + Math.min(prev[j], Math.min(cur[j - 1], prev[j - 1]));
        int[] t = prev; prev = cur; cur = t;
    }
    return prev[b.length()];
}

function editDistance(a, b) {
    let prev = Array.from({ length: b.length + 1 }, (_, j) => j);   // row i = 0
    for (let i = 1; i <= a.length; i++) {
        const cur = [i];
        for (let j = 1; j <= b.length; j++)
            cur[j] = a[i - 1] === b[j - 1] ? prev[j - 1]               // match: free
                   : 1 + Math.min(prev[j], cur[j - 1], prev[j - 1]);
        prev = cur;
    }
    return prev[b.length];
}

fn edit_distance(a: &[u8], b: &[u8]) -> usize {
    let mut prev: Vec<usize> = (0..=b.len()).collect();    // row i = 0
    for i in 1..=a.len() {
        let mut cur = vec![i; b.len() + 1];
        for j in 1..=b.len() {
            cur[j] = if a[i - 1] == b[j - 1] { prev[j - 1] }   // match: free
                     else { 1 + prev[j].min(cur[j - 1]).min(prev[j - 1]) };
        }
        prev = cur;
    }
    prev[b.len()]
}

editDistance :: String -> String -> Int
editDistance a b = last (foldl nextRow [0 .. length b] (zip [1 ..] a))   -- row i = 0 is 0, 1, 2, ...
  where
    -- row i from row i - 1, left to right; each cell reads diagonal, up and left
    nextRow prev (i, x) = row
      where
        row = i : zipWith3 cell b (zip prev (tail prev)) row
        cell y (diag, up) left
          | x == y = diag                                   -- match: free
          | otherwise = 1 + minimum [up, left, diag]

TimeO(n · m)

SpaceO(m) with two rows

The problem in this module asks for the same distance in six languages, with the full solution walkthrough.

Edit distance

The problem

State and recurrence

Bottom-up

Code and cost