Solving Edit Distance (Levenshtein) in JavaScript: Step-by-Step Guide

Edit distance is one of those classic computer science problems that shows up everywhere—from spell checkers to DNA sequence alignment to fuzzy search features in your favorite apps. In this tutorial, we'll break down the Levenshtein distance algorithm, understand how it works under the hood, and implement it in JavaScript from scratch.

What Is Levenshtein Distance?

The Levenshtein distance, named after Soviet mathematician Vladimir Levenshtein, measures the minimum number of single-character edits required to transform one string into another. The allowed operations are:

Insertion — adding a new character
Deletion — removing a character
Substitution — replacing one character with another

For example, transforming "kitten" into "sitting" requires three operations: substitute 'k' with 's', substitute 'e' with 'i', and insert 'g' at the end. So the Levenshtein distance is 3.

Why Edit Distance Matters

Edit distance is the backbone of many real-world features you interact with daily:

Spell checkers — suggesting corrections by finding dictionary words with minimal edit distance
Fuzzy search — returning results even when users mistype queries
DNA sequencing — comparing genetic sequences in bioinformatics
Plagiarism detection — measuring similarity between documents
Autocomplete systems — ranking suggestions by closeness to input
Data deduplication — identifying near-duplicate records in databases

Understanding this algorithm gives you a powerful tool for building intelligent text-processing features in your applications.

The Dynamic Programming Approach

The most efficient way to solve Levenshtein distance is through dynamic programming. The idea is to build a matrix where each cell [i][j] represents the edit distance between the first i characters of string A and the first j characters of string B.

Here's the recurrence relation:

If either string is empty, the distance equals the length of the other string (all insertions or deletions)
If the current characters match, the cost is 0 and we inherit the diagonal value
If they differ, we take the minimum of three operations (insert, delete, substitute) and add 1

Step-by-Step Implementation

Let's build the solution incrementally. First, here's the complete basic implementation:

function levenshteinDistance(str1, str2) {
  // Create a matrix of size (str1.length + 1) x (str2.length + 1)
  const m = str1.length;
  const n = str2.length;
  
  // Handle edge cases
  if (m === 0) return n;
  if (n === 0) return m;
  
  // Initialize the matrix
  const dp = Array.from({ length: m + 1 }, () => 
    new Array(n + 1).fill(0)
  );
  
  // Base cases: transforming to/from empty string
  for (let i = 0; i <= m; i++) {
    dp[i][0] = i;
  }
  for (let j = 0; j <= n; j++) {
    dp[0][j] = j;
  }
  
  // Fill the matrix
  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      // If characters match, no operation needed
      if (str1[i - 1] === str2[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1];
      } else {
        // Take minimum of insert, delete, or substitute
        dp[i][j] = 1 + Math.min(
          dp[i - 1][j],     // deletion
          dp[i][j - 1],     // insertion
          dp[i - 1][j - 1]  // substitution
        );
      }
    }
  }
  
  return dp[m][n];
}

// Test the function
console.log(levenshteinDistance("kitten", "sitting")); // Output: 3
console.log(levenshteinDistance("flaw", "lawn"));       // Output: 2
console.log(levenshteinDistance("", "abc"));            // Output: 3
console.log(levenshteinDistance("abc", "abc"));         // Output: 0

Let's trace through what happens with "kitten" and "sitting" to understand the matrix filling. The algorithm builds up a table where each cell represents the best solution for a sub-problem:

    ""  s  i  t  t  i  n  g
""   0  1  2  3  4  5  6  7
k    1  1  2  3  4  5  6  7
i    2  2  1  2  3  4  5  6
t    3  3  2  1  2  3  4  5
t    4  4  3  2  1  2  3  4
e    5  5  4  3  2  2  3  4
n    6  6  5  4  3  3  2  3

The bottom-right cell gives us our answer: 3. Each cell was computed by looking at its left, top, and top-left neighbors.

Space-Optimized Version

The basic implementation uses O(m × n) space. However, since we only ever need the previous row to compute the current row, we can reduce space complexity to O(min(m, n)):

function levenshteinDistanceOptimized(str1, str2) {
  // Ensure str1 is the shorter string for less memory usage
  if (str1.length > str2.length) {
    [str1, str2] = [str2, str1];
  }
  
  const m = str1.length;
  const n = str2.length;
  
  if (m === 0) return n;
  
  // Only keep two rows in memory
  let previousRow = Array.from({ length: m + 1 }, (_, i) => i);
  let currentRow = new Array(m + 1).fill(0);
  
  for (let j = 1; j <= n; j++) {
    currentRow[0] = j;
    
    for (let i = 1; i <= m; i++) {
      if (str1[i - 1] === str2[j - 1]) {
        currentRow[i] = previousRow[i - 1];
      } else {
        currentRow[i] = 1 + Math.min(
          previousRow[i],      // deletion
          currentRow[i - 1],   // insertion
          previousRow[i - 1]   // substitution
        );
      }
    }
    
    // Swap rows for next iteration
    [previousRow, currentRow] = [currentRow, previousRow];
  }
  
  return previousRow[m];
}

console.log(levenshteinDistanceOptimized("kitten", "sitting")); // Output: 3

This version is particularly useful when working with very long strings where memory becomes a constraint.

Computing Similarity Percentage

Often, you don't just want the raw distance—you want a similarity score between 0 and 1 (or 0% to 100%). Here's how to convert edit distance into a normalized similarity:

function similarityScore(str1, str2) {
  const distance = levenshteinDistance(str1, str2);
  const maxLength = Math.max(str1.length, str2.length);
  
  if (maxLength === 0) return 1.0; // Both strings are empty
  
  return 1.0 - (distance / maxLength);
}

function similarityPercentage(str1, str2) {
  return (similarityScore(str1, str2) * 100).toFixed(2) + "%";
}

console.log(similarityScore("kitten", "sitting"));           // 0.5714...
console.log(similarityPercentage("javascript", "javascrpt")); // 90.00%
console.log(similarityPercentage("hello", "hello"));          // 100.00%

Building a Fuzzy Search Function

Now let's put our Levenshtein implementation to practical use by building a fuzzy search function that finds the closest matching words from a list:

function fuzzySearch(query, wordList, threshold = 0.6) {
  return wordList
    .map(word => ({
      word,
      similarity: similarityScore(query.toLowerCase(), word.toLowerCase())
    }))
    .filter(result => result.similarity >= threshold)
    .sort((a, b) => b.similarity - a.similarity)
    .map(result => result.word);
}

const dictionary = [
  "apple", "banana", "orange", "grape", 
  "apricot", "pineapple", "application", "snapple"
];

console.log(fuzzySearch("aple", dictionary));
// Output: ["apple", "snapple", "apricot", "grape"]

console.log(fuzzySearch("banan", dictionary));
// Output: ["banana"]

Implementing a Simple Spell Checker

Here's another practical application—a basic spell checker that suggests corrections:

class SpellChecker {
  constructor(dictionary) {
    this.dictionary = dictionary;
  }
  
  check(word) {
    const lowerWord = word.toLowerCase();
    
    // Exact match found
    if (this.dictionary.includes(lowerWord)) {
      return { correct: true, word, suggestions: [] };
    }
    
    // Find closest matches
    const suggestions = this.dictionary
      .map(dictWord => ({
        word: dictWord,
        distance: levenshteinDistance(lowerWord, dictWord)
      }))
      .filter(item => item.distance <= 3)
      .sort((a, b) => a.distance - b.distance)
      .slice(0, 5)
      .map(item => item.word);
    
    return { correct: false, word, suggestions };
  }
}

const spellChecker = new SpellChecker([
  "hello", "world", "javascript", "programming",
  "algorithm", "function", "variable", "object"
]);

console.log(spellChecker.check("helo"));
// { correct: false, word: "helo", suggestions: ["hello"] }

console.log(spellChecker.check("javascrpt"));
// { correct: false, word: "javascrpt", suggestions: ["javascript"] }

console.log(spellChecker.check("function"));
// { correct: true, word: "function", suggestions: [] }

Handling Unicode and Special Characters

The basic implementation treats each character as a single unit, which breaks with multi-byte Unicode characters or emoji. Here's a Unicode-aware version:

function levenshteinDistanceUnicode(str1, str2) {
  // Convert strings to arrays of code points
  const arr1 = [...str1];
  const arr2 = [...str2];
  
  const m = arr1.length;
  const n = arr2.length;
  
  if (m === 0) return n;
  if (n === 0) return m;
  
  const dp = Array.from({ length: m + 1 }, () => 
    new Array(n + 1).fill(0)
  );
  
  for (let i = 0; i <= m; i++) dp[i][0] = i;
  for (let j = 0; j <= n; j++) dp[0][j] = j;
  
  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (arr1[i - 1] === arr2[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1];
      } else {
        dp[i][j] = 1 + Math.min(
          dp[i - 1][j],
          dp[i][j - 1],
          dp[i - 1][j - 1]
        );
      }
    }
  }
  
  return dp[m][n];
}

console.log(levenshteinDistanceUnicode("café", "cafe"));   // Output: 1
console.log(levenshteinDistanceUnicode("😀😁", "😀😂"));   // Output: 1

Using the spread operator [...str] correctly splits strings into Unicode code points rather than UTF-16 code units, ensuring emoji and accented characters are handled properly.

Best Practices

When working with Levenshtein distance in production applications, keep these guidelines in mind:

Normalize inputs first — convert to lowercase, trim whitespace, and remove diacritics before comparing to avoid false differences
Use the space-optimized version for long strings to avoid memory issues
Consider early termination — if you only need to know if distance is below a threshold, you can stop early once all values in a row exceed it
Cache results — if you're comparing the same strings repeatedly, memoize the function
Consider alternative algorithms for specific use cases — Damerau-Levenshtein adds transposition as an operation, and Jaro-Winkler is better for short strings like names
Profile performance — Levenshtein is O(m × n), which can be expensive for very long strings or large-scale comparisons
Use Web Workers for heavy computations in browser applications to avoid blocking the main thread

Here's an example of memoization to cache results:

function memoizedLevenshtein() {
  const cache = new Map();
  
  return function(str1, str2) {
    const key = `${str1}|${str2}`;
    
    if (cache.has(key)) {
      return cache.get(key);
    }
    
    const result = levenshteinDistance(str1, str2);
    cache.set(key, result);
    
    return result;
  };
}

const memoLevenshtein = memoizedLevenshtein();
console.log(memoLevenshtein("kitten", "sitting")); // Computes
console.log(memoLevenshtein("kitten", "sitting")); // Returns cached result

Performance Considerations

The time complexity of the standard Levenshtein algorithm is O(m × n), where m and n are the lengths of the two strings. For most practical text-processing tasks, this is perfectly acceptable. However, if you're comparing very long strings or running comparisons at scale, consider these optimizations:

// Early exit version for threshold-based comparisons
function isWithinDistance(str1, str2, maxDistance) {
  const m = str1.length;
  const n = str2.length;
  
  // Quick length check
  if (Math.abs(m - n) > maxDistance) return false;
  
  let previousRow = Array.from({ length: m + 1 }, (_, i) => i);
  
  for (let j = 1; j <= n; j++) {
    let currentRow = [j];
    let rowMin = j;
    
    for (let i = 1; i <= m; i++) {
      if (str1[i - 1] === str2[j - 1]) {
        currentRow[i] = previousRow[i - 1];
      } else {
        currentRow[i] = 1 + Math.min(
          previousRow[i],
          currentRow[i - 1],
          previousRow[i - 1]
        );
      }
      rowMin = Math.min(rowMin, currentRow[i]);
    }
    
    // If minimum value in row exceeds threshold, exit early
    if (rowMin > maxDistance) return false;
    
    previousRow = currentRow;
  }
  
  return previousRow[m] <= maxDistance;
}

console.log(isWithinDistance("cat", "bat", 1));    // true
console.log(isWithinDistance("cat", "dog", 1));    // false

This early-exit approach can dramatically reduce computation time when you only need to know if two strings are "close enough" rather than computing the exact distance.

Conclusion

The Levenshtein distance algorithm is a fundamental tool every developer should have in their toolkit. We've walked through what it is, why it matters, and how to implement it in JavaScript—from the basic dynamic programming solution to space-optimized and Unicode-aware variants. We also explored practical applications like fuzzy search and spell checking, along with performance optimizations for production use. Whether you're building a search feature, a spell checker, or any system that needs to understand string similarity, the Levenshtein algorithm provides a reliable, well-understood foundation. Start with the basic implementation, profile it against your actual data, and apply the optimizations we discussed as your needs evolve. With this knowledge, you're well-equipped to add intelligent text-matching capabilities to your JavaScript applications.