Damerau-Levenshtein distance: Examples & Code

Algorithm Visualizations November 16, 2026 javascript

Published by Dimitris Kougioumtzis · Updated

Allow insertions, deletions, substitutions and adjacent transpositions, including repeated edits of the same substring.

Track the last source occurrence of each target character and the last matching target column in the current row. Compare ordinary edit steps with a transposition spanning those earlier occurrences.

Open the 3D visualization

Damerau-Levenshtein distance example state preview
Preview of the example's final state. Complete values are available in the worked example and interactive timeline.

When to use Damerau-Levenshtein distance

Measuring spelling differences when swapped adjacent characters should count as one edit.

Choosing an alternative

Restricted optimal-string-alignment distance forbids editing a substring repeatedly. This unrestricted variant allows repeated edits: ca to abc costs two, whereas restricted OSA costs three.

Worked example: input and state changes

Example input

ca | abc

These checkpoints follow the actual example timeline. State details show the stored values and decisions; use the visualization to inspect every intervening step.

  1. Step 0: Initialize guarded distance matrix; outer row/column hold infinity.

    State at this checkpoint
    {
      "values": [
        5,
        5,
        5,
        5,
        5,
        5,
        0,
        1,
        2,
        3,
        5,
        1,
        0,
        0,
        0,
        5,
        2,
        0,
        0,
        0
      ],
      "active": [],
      "kind": "matrix",
      "columns": 5,
      "result": 0
    }
  2. Step 2: Compare ordinary edits with transposition via last matching rows 0, 0.

    State at this checkpoint
    {
      "values": [
        5,
        5,
        5,
        5,
        5,
        5,
        0,
        1,
        2,
        3,
        5,
        1,
        1,
        2,
        0,
        5,
        2,
        0,
        0,
        0
      ],
      "active": [
        13,
        0
      ],
      "kind": "matrix",
      "columns": 5,
      "result": 0
    }
  3. Step 4: Compare ordinary edits with transposition via last matching rows 0, 0.

    State at this checkpoint
    {
      "values": [
        5,
        5,
        5,
        5,
        5,
        5,
        0,
        1,
        2,
        3,
        5,
        1,
        1,
        2,
        2,
        5,
        2,
        1,
        0,
        0
      ],
      "active": [
        17,
        0
      ],
      "kind": "matrix",
      "columns": 5,
      "result": 0
    }
  4. Step 5: Compare ordinary edits with transposition via last matching rows 0, 1.

    State at this checkpoint
    {
      "values": [
        5,
        5,
        5,
        5,
        5,
        5,
        0,
        1,
        2,
        3,
        5,
        1,
        1,
        2,
        2,
        5,
        2,
        1,
        2,
        0
      ],
      "active": [
        18,
        1
      ],
      "kind": "matrix",
      "columns": 5,
      "result": 0
    }
  5. Step 7: Unrestricted Damerau-Levenshtein distance: 2.

    State at this checkpoint
    {
      "values": [
        5,
        5,
        5,
        5,
        5,
        5,
        0,
        1,
        2,
        3,
        5,
        1,
        1,
        2,
        2,
        5,
        2,
        1,
        2,
        2
      ],
      "active": [],
      "kind": "matrix",
      "columns": 5,
      "result": 2
    }

Expected final state

Unrestricted Damerau-Levenshtein distance: 2.

Complexity and input bounds

Family: Strings. Time complexity: O(nm) time and space.

Implementation detail: Unit insertion, deletion, substitution and adjacent transposition costs; strings contain up to twelve lowercase letters and can be empty. Downloads use a guarded matrix of at most 196 cells and return distance only. This view does not reconstruct a transposition alignment.

Space complexity: O(nm + alphabet size) auxiliary storage plus recorded matrix frames.

Working-space bounds describe algorithm state and any explicitly noted output, excluding the visualization's saved timeline. Recording frames can use more memory than running the function alone. Here n is sequence length, V and E are vertex and edge counts, and other parameters refer to the named input dimensions.

source | target; each 0..12 lowercase letters. Unrestricted distance; this is not optimal-string-alignment distance.

The playground validates these limits before starting. Downloaded functions are callable implementations, with parameter and output-buffer contracts in their comments; they do not all repeat the playground's input validation.

Common mistakes and limitations

Do not replace the last-occurrence recurrence with a two-cell transposition shortcut. Initialize the infinity guard row and column, and update last source occurrences after completing each row.

Further reading

For background on algorithm analysis and the JavaScript function interface:

Editorial and testing approach · Browse all algorithm guides

Complete JavaScript implementation

javascript
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
// Lowercase ASCII integer arrays a/b with n/m 0..12; empty strings supported. Returns unrestricted Damerau-Levenshtein distance with unit insertion, deletion, substitution and adjacent transposition costs. Maintains last occurrences and a guarded (n+2)*(m+2) matrix; repeated edits of a substring are allowed. This is not restricted optimal-string-alignment distance: ca -> abc costs 2. O(nm) time and space. Reference snippets assume validated playground inputs. Fixed scratch buffers have 256 slots. Sorting variants may use a different traversal strategy than the animation.
function algorithm(a, n, b, m) {
    let d = Array(256).fill(0); let last = Array(256).fill(0); let s = m+2; let inf = n+m; let matched = 0; let i1 = 0; let j1 = 0; let cost = 0; let value = 0; let trans = 0;
    d[0] = inf;
    for (let i = 0; i <= n; i++) { d[(i+1)*s] = inf; d[(i+1)*s+1] = i; }
    for (let j = 0; j <= m; j++) { d[j+1] = inf; d[s+j+1] = j; }
    for (let i = 1; i <= n; i++) { matched = 0; for (let j = 1; j <= m; j++) { i1 = last[b[j-1]]; j1 = matched; cost = 1; if (a[i-1] == b[j-1]) { cost = 0; matched = j; }
     value = d[i*s+j]+cost; if (d[(i+1)*s+j]+1 < value) { value = d[(i+1)*s+j]+1; } if (d[i*s+j+1]+1 < value) { value = d[i*s+j+1]+1; }
     trans = d[i1*s+j1]+(i-i1-1)+1+(j-j1-1); if (trans < value) { value = trans; } d[(i+1)*s+j+1] = value;
     } last[a[i-1]] = i; }
    return d[(n+1)*s+m+1];
}

Source

The Lowrance-Wagner extension supplies the unrestricted adjacent-transposition recurrence. The playground uses unit costs satisfying the paper cost restrictions, not restricted optimal-string-alignment distance.