Edit Distance (Levenshtein) Calculator

What Edit Distance Measures

Levenshtein distance, named after Soviet mathematician Vladimir Levenshtein who introduced it in 1965, counts the minimum number of single-character edits (insertions, deletions, or substitutions) needed to transform one string into another. Transforming "kitten" into "sitting" requires 3 edits, substitute k→s, substitute e→i, and insert g, giving a Levenshtein distance of 3. A distance of 0 means the strings are identical.

How the Algorithm Works

The standard algorithm uses dynamic programming, building a table where each cell represents the edit distance between prefixes of the two strings. Rather than trying every possible sequence of edits (which would be computationally explosive for longer strings), the table builds up the answer incrementally from smaller subproblems, giving an efficient O(m×n) time complexity where m and n are the string lengths, this is the same fundamental technique (dynamic programming) used across many classic computer science problems.

Real-World Applications

• Spell checkers: when you misspell a word, the checker finds dictionary words with the smallest edit distance to suggest corrections.
• Fuzzy search and deduplication: matching "John Smith" and "Jon Smyth" as likely the same person in a database despite spelling differences.
• DNA and protein sequence comparison: bioinformatics uses variants of edit distance to measure genetic similarity between sequences.
• Plagiarism and near-duplicate detection: identifying text that has been lightly modified from an original source.
• Autocomplete and search-as-you-type: ranking suggestions by how close they are to what a user has typed so far.

Edit Distance vs Other Similarity Metrics

Levenshtein distance operates purely on character-level edits, unaware of word meaning or semantic similarity, "cat" and "bat" have a small edit distance despite being unrelated animals, while "cat" and "feline" have a large edit distance despite meaning almost the same thing. For semantic similarity (comparing meaning rather than spelling), embedding-based methods using cosine similarity are the modern standard. Edit distance remains the right tool specifically when you care about surface-level character similarity, typos, near-duplicates, and fuzzy string matching, not conceptual meaning.