Levenshtein Distance: Fuzzy Keyword Matcher
Search engines and CLI tools forgive typing mistakes using edit distance. The Levenshtein distance dynamic programming algorithm computes the minimum number of single-character insertions, deletions, and substitutions needed to turn string $A$ into string $B$ in $O(M \times N)$ time and $O(\min(M, N))$ space 🔤🎯⚡.
def edit_distance(s1, s2):
prev = list(range(len(s2) + 1))
for c1 in s1:
curr = [prev[0] + 1] * (len(s2) + 1)
for j, c2 in enumerate(s2):
cost = 0 if c1 == c2 else 1
curr[j + 1] = min(curr[j] + 1, prev[j + 1] + 1, prev[j] + cost)
prev = curr
return prev[-1]
print("Distance between 'python' and 'pythn':", edit_distance("python", "pythn"))
# 9. Levenshtein Distance: Fuzzy Keyword Matcher When a user types `git branhc` instead of `git branch`, Git doesn't just crash with a generic error; it asks: *"Did you mean 'branch'?"*. Building high-quality developer tooling requires fuzzy matching typo tolerance 🛑. ```python # The Levenshtein Operations: # 1. Insertion: Add a character ("cat" -> "cats", dist = 1) # 2. Deletion: Drop a character ("cats" -> "cat", dist = 1) # 3. Substitution: Swap a character ("cat" -> "bat", dist = 1) # # kitten -> sitting: # 1. k -> s (sitten) [Sub 1] # 2. e -> i (sittin) [Sub 2] # 3. + g (sitting) [Ins 3] # Total Distance = 3 ``` ### Memory Optimization: Rolling Array A naive matrix allocates an $(M+1) \times (N+1)$ grid in memory. For two 10,000-character strings, that allocates $100{,}000{,}000$ integers! By observing that row $i$ only depends on row $i-1$, we swap between two alternating rows (`prev_row` and `curr_row`), dropping memory consumption to strictly $O(\min(M, N))$ 🔤🎯⚡. --- ### Interactive Pop-Quiz 🧠#### What is the minimum number of character edits needed to transform the string `kitten` into `sitting`? - [ ] 3 edits (substitute 'k'->'s', substitute 'e'->'i', insert 'g') 🎯 - [ ] 1 edit - [ ] 5 edits - [ ] 0 edits (they are anagrams) --- ### Practical Challenge 🎯 Implement `levenshtein_distance(s1: str, s2: str) -> int` using a space-optimized two-row dynamic programming array ($O(\min(M, N))$ space). Verify distance between `'kitten'` and `'sitting'` is 3, `'python'` and `'pthon'` is 1, and identical strings yield 0. Print results. <details> <summary>Solution</summary> ```python def levenshtein_distance(s1: str, s2: str) -> int: if len(s1) < len(s2): s1, s2 = s2, s1 # s2 is the shorter string -> O(min(M, N)) space prev_row = list(range(len(s2) + 1)) for i, c1 in enumerate(s1): curr_row = [i + 1] * (len(s2) + 1) for j, c2 in enumerate(s2): cost = 0 if c1 == c2 else 1 curr_row[j + 1] = min( curr_row[j] + 1, # Insertion prev_row[j + 1] + 1, # Deletion prev_row[j] + cost # Substitution ) prev_row = curr_row return prev_row[-1] d1 = levenshtein_distance("kitten", "sitting") d2 = levenshtein_distance("python", "pthon") d3 = levenshtein_distance("xicae", "xicae") assert d1 == 3 assert d2 == 1 assert d3 == 0 print(f"Levenshtein verified: kitten->sitting: {d1}, python->pthon: {d2}") ``` </details>