Word 1

Word 2

computing comparing traceback

1 / 53

Speed

Compute the Levenshtein distance between "KITTEN" (6) and "SITTING" (7). Row index i = first i characters of "KITTEN", column index j = first j characters of "SITTING".

Distance

Edits

Table size

7×8

Step

1/53

edit-distance.js

1function editDistance(w1, w2) {

2 const m = w1.length, n = w2.length;

4 // dp[i][j] = dist(w1[0..i), w2[0..j)

5 for (let i = 0; i <= m; i++) dp[i][0] = i;

6 for (let j = 0; j <= n; j++) dp[0][j] = j;

8 for (let i = 1; i <= m; i++)

9 for (let j = 1; j <= n; j++) {

10 if (w1[i-1] === w2[j-1])

11 dp[i][j] = dp[i-1][j-1]; // match

12 else

13 dp[i][j] = 1 + Math.min(

14 dp[i-1][j], // delete

15 dp[i][j-1], // insert

16 dp[i-1][j-1] // substitute

17 );

18 }

19 return dp[m][n];

20}

Edit either word (A–Z, max 8 chars) · Presets load classic examples · Any step is shareable via the URL

About the Edit Distance (Levenshtein) algorithm

Minimum insertions, deletions, and substitutions to transform one string into another. The classic 2D DP with traceback for the exact edit script.

Category: Dynamic Programming
Difficulty: Medium
Time complexity: O(m·n)
Space complexity: O(m·n)
Introduced: 1965