The Levenshtein algorithm computes the edit distance between two strings: the minimum number of single-character edits required to transform one string into the other.

Allowed operations are:

• insertion
• deletion
• substitution

It is commonly used in spell checkers, fuzzy search, OCR cleanup, and typo-tolerant matching.

Core Idea

Levenshtein uses dynamic programming. Build a matrix where:

• rows represent characters of string A
• columns represent characters of string B
• each cell stores the minimum edit cost up to that point

The final cell gives the distance.

Recurrence

For dp[i][j]:

• if characters match, cost is dp[i - 1][j - 1]
• otherwise take 1 + min(
  • dp[i - 1][j] (deletion),
  • dp[i][j - 1] (insertion),
  • dp[i - 1][j - 1] (substitution)
  • )

JavaScript Implementation

export function levenshteinDistance(a, b) {
  if (typeof a !== "string" || typeof b !== "string") {
    throw new TypeError("Inputs must be strings")
  }

  const rows = a.length + 1
  const cols = b.length + 1

  const dp = Array.from({ length: rows }, () => Array(cols).fill(0))

  for (let i = 0; i < rows; i += 1) dp[i][0] = i
  for (let j = 0; j < cols; j += 1) dp[0][j] = j

  for (let i = 1; i < rows; i += 1) {
    for (let j = 1; j < cols; j += 1) {
      const cost = a[i - 1] === b[j - 1] ? 0 : 1

      dp[i][j] = Math.min(
        dp[i - 1][j] + 1,
        dp[i][j - 1] + 1,
        dp[i - 1][j - 1] + cost
      )
    }
  }

  return dp[a.length][b.length]
}

Example

console.log(levenshteinDistance("kitten", "sitting")) // 3
console.log(levenshteinDistance("flaw", "lawn")) // 2

Similarity Score (Optional)

You can convert distance to a normalized similarity score:

function levenshteinSimilarity(a, b) {
  const distance = levenshteinDistance(a, b)
  const maxLen = Math.max(a.length, b.length)

  if (maxLen === 0) return 1

  return 1 - distance / maxLen
}

This returns a value between 0 and 1.

Practical Notes

• Time complexity is O(m * n) for strings of length m and n.
• Memory can be optimized to two rows if you only need the final distance.
• For ranking many candidates, combine Levenshtein with indexing or prefix filters.

Final Take

Use Levenshtein when you need typo-tolerant matching and a clear edit-based measure of string difference. It is simple, interpretable, and effective in many real-world text pipelines.