String Similarity Calculator

Levenshtein distance (edit distance) is the minimum number of single-character edits needed to transform one string into another. The three allowed operations are: insertion (add a character), deletion (remove a character), substitution (replace one character with another). Example: "kitten" → "sitting" requires 3 operations: k→s, e→i, +g. Named after Vladimir Levenshtein who described this algorithm in 1965. Applications: spell checking, DNA sequence alignment, natural language processing, fuzzy string matching.

Similarity % = (1 − editDistance / max(len1, len2)) × 100. This normalizes the distance relative to the longest string. Example: distance = 2, max length = 8 → similarity = (1 − 2/8) × 100 = 75%. A distance of 0 means identical strings (100% similar). A distance equal to max length means completely different strings (0% similar). Other similarity metrics include Jaro-Winkler (weights initial character agreement more highly) and cosine similarity (for token-based comparison).

Damerau-Levenshtein extends Levenshtein by adding a fourth operation: transposition (swap two adjacent characters). Example: "ab" → "ba" has Levenshtein distance 2 (delete + insert) but Damerau-Levenshtein distance 1 (one transposition). This is important for spell-checking since many typos are transpositions ("teh" → "the"). There are two variants: restricted (adjacent transpositions only) and unrestricted (any transpositions). This tool uses standard Levenshtein (no transpositions).

Spell checkers: suggest words with low edit distance from the misspelled word. DNA sequencing: align nucleotide sequences to find mutations and insertions. Version control: git diff uses edit distance algorithms to show line-level changes. Natural language processing: named entity disambiguation, coreference resolution. Fraud detection: detect name variations (typosquatting, identity fraud). Record linkage: match records across databases when names/addresses vary slightly. OCR correction: fix optical character recognition errors.

The Wagner-Fischer algorithm computes Levenshtein distance using dynamic programming with time O(m×n) and space O(m×n) where m,n are string lengths. It builds a matrix where cell [i][j] = edit distance between the first i characters of string 1 and first j characters of string 2. Base cases: row 0 = 0..n (delete all chars of s1), col 0 = 0..m (insert all chars of s2). Recurrence: if s1[i] == s2[j], cell = previous diagonal; otherwise cell = 1 + min(left, above, diagonal). Space can be optimized to O(min(m,n)) using two rows.