String A: "kitten"    String B: "sitting"
 
Transformation (one of many possible):
  kitten
  sitten  (replace 'k' with 's')
  sittin  (replace 'e' with 'i')
  sitting (insert 'g')
 
Edit distance: 3
 
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
 
String A: "cat"        String B: "car"
 
Transformation:
  cat
  car  (replace 't' with 'r')
 
Edit distance: 1
 
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
 
String A: "abc"        String B: "abc"
 
No changes needed.
 
Edit distance: 0
 
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
 
String A: "hello"      String B: ""
 
Delete all 5 characters.
 
Edit distance: 5

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72

def edit_distance(s1: str, s2: str) -> int:
    """
    Compute the Levenshtein (edit) distance between two strings.
    
    Time Complexity: O(m × n) where m = len(s1), n = len(s2)
    Space Complexity: O(m × n) for the DP table
    """
    m, n = len(s1), len(s2)
    
    # dp[i][j] = edit distance between s1[0:i] and s2[0:j]
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    # Base cases: transforming to/from empty string
    for i in range(m + 1):
        dp[i][0] = i  # Delete i characters
    for j in range(n + 1):
        dp[0][j] = j  # Insert j characters
    
    # Fill the table
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s1[i - 1] == s2[j - 1]:
                # Characters match, no operation needed
                dp[i][j] = dp[i - 1][j - 1]
            else:
                # Take minimum of three operations
                dp[i][j] = 1 + min(
                    dp[i - 1][j],      # Delete from s1
                    dp[i][j - 1],      # Insert to s1
                    dp[i - 1][j - 1]   # Replace
                )
    
    return dp[m][n]
 
 
def edit_distance_space_optimized(s1: str, s2: str) -> int:
    """
    Space-optimized version using only O(min(m, n)) space.
    
    Observation: Each row only depends on the previous row.
    """
    # Ensure s1 is the longer string to minimize space
    if len(s1) < len(s2):
        s1, s2 = s2, s1
    
    m, n = len(s1), len(s2)
    
    # Only need two rows
    prev = list(range(n + 1))
    curr = [0] * (n + 1)
    
    for i in range(1, m + 1):
        curr[0] = i
        for j in range(1, n + 1):
            if s1[i - 1] == s2[j - 1]:
                curr[j] = prev[j - 1]
            else:
                curr[j] = 1 + min(prev[j], curr[j - 1], prev[j - 1])
        prev, curr = curr, prev
    
    return prev[n]
 
 
# Visualization of DP table for "cat" → "car":
#
#       ""  c   a   r
#   ""   0  1   2   3
#   c    1  0   1   2
#   a    2  1   0   1
#   t    3  2   1   1  ← edit distance
#
# Reading the answer: dp[3][3] = 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

def naive_spell_check(word: str, dictionary: list[str], max_dist: int = 2) -> list[str]:
    """
    Naive spell checker - DO NOT USE IN PRODUCTION.
    
    Time Complexity: O(D × m × n)
                     D = dictionary size
                     m = word length
                     n = average dictionary word length
    
    For a 100,000 word dictionary and word length 10:
    ~100,000 × 10 × 10 = 10,000,000 operations per query
    """
    suggestions = []
    
    for dict_word in dictionary:
        dist = edit_distance(word, dict_word)
        if dist <= max_dist:
            suggestions.append((dict_word, dist))
    
    # Sort by distance, then alphabetically
    suggestions.sort(key=lambda x: (x[0], x[1]))
    return [word for word, dist in suggestions]
 
 
# The problem:
# - English dictionary: ~170,000 words
# - Average query takes 10M+ operations
# - User expects suggestions in <100ms
# - At 1M operations/ms, that's 10ms just for one query
# - Multiple suggestions + ranking = unacceptable latency

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108

class TrieNode:
    """Trie node for spell checker."""
    __slots__ = ['children', 'word']
    
    def __init__(self):
        self.children: dict[str, 'TrieNode'] = {}
        self.word: str | None = None  # Stores word at end nodes
 
 
class SpellChecker:
    """
    Trie-based spell checker with edit distance pruning.
    
    Build Time: O(sum of dictionary word lengths)
    Query Time: O(A^k × m) where A = alphabet size, k = max distance, m = word length
                In practice, much faster due to pruning
    Space: O(total dictionary characters)
    """
    
    def __init__(self, dictionary: list[str]):
        self.root = TrieNode()
        for word in dictionary:
            self._insert(word)
    
    def _insert(self, word: str) -> None:
        """Insert a word into the trie."""
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.word = word
    
    def suggest(self, word: str, max_distance: int = 2) -> list[tuple[str, int]]:
        """
        Find all dictionary words within max_distance edits of word.
        
        Returns list of (suggested_word, edit_distance) tuples.
        """
        suggestions = []
        word_len = len(word)
        
        # Initial DP row: distance from empty string to word prefixes
        # dp_row[j] = distance to transform "" to word[0:j]
        initial_row = list(range(word_len + 1))
        
        def search(node: TrieNode, prev_row: list[int], depth: int) -> None:
            """
            DFS through trie, computing edit distance row at each step.
            
            node: Current trie node
            prev_row: DP row from parent (represents distances for current prefix)
            depth: Current depth in trie (length of trie path so far)
            """
            # Check if current node completes a word
            if node.word is not None:
                # Distance to transform this word to input word
                final_distance = prev_row[-1]
                if final_distance <= max_distance:
                    suggestions.append((node.word, final_distance))
            
            # Explore children
            for char, child in node.children.items():
                # Compute new DP row for this character
                curr_row = [depth + 1]  # First cell: distance from trie-prefix to ""
                
                for j in range(1, word_len + 1):
                    if word[j - 1] == char:
                        # Characters match
                        cost = prev_row[j - 1]
                    else:
                        # Minimum of insert, delete, replace
                        cost = 1 + min(
                            prev_row[j],      # Delete from trie word
                            curr_row[j - 1],  # Insert to trie word
                            prev_row[j - 1]   # Replace
                        )
                    curr_row.append(cost)
                
                # PRUNING: Only continue if some distance is within threshold
                if min(curr_row) <= max_distance:
                    search(child, curr_row, depth + 1)
        
        # Start search from root
        search(self.root, initial_row, 0)
        
        # Sort by distance, then alphabetically
        suggestions.sort(key=lambda x: (x[1], x[0]))
        return suggestions
    
    def check(self, word: str) -> bool:
        """Check if word exists in dictionary (exact match)."""
        node = self.root
        for char in word:
            if char not in node.children:
                return False
            node = node.children[char]
        return node.word is not None
 
 
# Example usage:
dictionary = ["cat", "car", "cart", "care", "card", "bat", "bar", "bark"]
checker = SpellChecker(dictionary)
 
print(checker.check("cat"))  # True
print(checker.check("cta"))  # False (misspelling)
print(checker.suggest("cta", max_distance=1))  # [('cat', 1)]
print(checker.suggest("cta", max_distance=2))  # [('cat', 1), ('car', 2)]

Input word: "cta" (we want suggestions for this misspelling)
Max distance: 1
 
Initial DP row at root (depth 0):
┌─────────────────────────────────────────┐
│ Position:  ""   c    t    a             │
│ Index:      0   1    2    3             │
│ Value:      0   1    2    3             │
└─────────────────────────────────────────┘
Interpretation: Distance from "" (empty trie prefix) to "c", "ct", "cta"
 
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
 
At node 'c' (depth 1):
Previous row: [0, 1, 2, 3]
 
Computing new row for char 'c':
• curr_row[0] = depth = 1 (distance from "c" to "")
• word[0]='c' matches 'c': curr_row[1] = prev[0] = 0
• word[1]='t' ≠ 'c': curr_row[2] = 1 + min(prev[2]=2, curr[1]=0, prev[1]=1) = 1
• word[2]='a' ≠ 'c': curr_row[3] = 1 + min(prev[3]=3, curr[2]=1, prev[2]=2) = 2
 
New row: [1, 0, 1, 2]
┌─────────────────────────────────────────┐
│ Position:  ""   c    t    a             │
│ Index:      0   1    2    3             │
│ Value:      1   0    1    2             │
└─────────────────────────────────────────┘
min(row) = 0 ≤ 1 → Continue exploring!
 
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
 
At node 'a' (depth 2), under 'c':
Previous row: [1, 0, 1, 2]
 
Computing new row for char 'a':
• curr_row[0] = depth = 2
• word[0]='c' ≠ 'a': curr_row[1] = 1 + min(prev[1]=0, curr[0]=2, prev[0]=1) = 1
• word[1]='t' ≠ 'a': curr_row[2] = 1 + min(prev[2]=1, curr[1]=1, prev[1]=0) = 1
• word[2]='a' matches 'a': curr_row[3] = prev[2] = 1
 
New row: [2, 1, 1, 1]
┌─────────────────────────────────────────┐
│ Position:  ""   c    t    a             │
│ Value:      2   1    1    1             │
└─────────────────────────────────────────┘
min(row) = 1 ≤ 1 → Continue exploring!
 
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
 
At node 't' (depth 3), under 'ca':
Previous row: [2, 1, 1, 1]
This node has node.word = "cat"
 
Computing new row for char 't':
• curr_row[0] = 3
• word[0]='c' ≠ 't': curr_row[1] = 1 + min(1, 3, 2) = 2
• word[1]='t' matches 't': curr_row[2] = prev[1] = 1  
• word[2]='a' ≠ 't': curr_row[3] = 1 + min(1, 1, 1) = 2
 
New row: [3, 2, 1, 2]
              ↑
         This is the distance from "cat" to "cta" at curr_row[-1] = 2
 
But wait! curr_row[-1] = 2 > max_distance = 1
Hmm, but we also found suggestions while exploring...
 
Actually wait: Let me recalculate with the final cell being what matters for word completion:
 
At "cat" (word ends here): prev_row[-1] = curr_row[-1] = 2 > 1
So "cat" is NOT suggested (distance 2 > max_distance 1)? 
 
Let me reconsider... The algorithm checks prev_row[-1] ≤ max_distance.
With max_distance=2, "cat" WOULD be suggested with distance 1.
 
Actually I made an error. Let me redo this more carefully.
 
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
 
CORRECT TRACE with max_distance = 2:
 
At node 't' (word "cat"):
Final row: [3, 2, 1, 2]
             │     │
             │     └── Distance from "cat" to "cta" = 2 (swap t↔a? No, it's 1 transposition but we count insert+delete)
             └── Actually this is right!
 
Wait, edit_distance("cat", "cta") should be:
cat → cta: 
  - just swap 't' and 'a'
  - but Levenshtein counts: delete 't', delete 'a', insert 'a', insert 't' = 4? No...
  - Or: replace position 1 'a'→'t', replace position 2 't'→'a' = 2
 
Yes! edit_distance("cat", "cta") = 2 (two replacements)
 
With max_distance=2: prev_row[-1] = 2 ≤ 2 → "cat" IS suggested!
With max_distance=1: "cat" is NOT suggested
 
This demonstrates the algorithm correctly!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141

from collections import defaultdict
import math
 
class AdvancedSpellChecker:
    """
    Production-grade spell checker with frequency-based ranking.
    """
    
    def __init__(self, dictionary: list[str], frequencies: dict[str, int] = None):
        """
        Args:
            dictionary: List of valid words
            frequencies: Optional word → frequency mapping
        """
        self.trie_root = {}
        self.END = '#'
        self.frequencies = frequencies or {}
        
        # Build trie
        for word in dictionary:
            node = self.trie_root
            for char in word:
                node = node.setdefault(char, {})
            node[self.END] = word
        
        # Compute frequency stats for scoring
        if frequencies:
            total = sum(frequencies.values())
            self.log_freqs = {
                w: math.log(f / total) for w, f in frequencies.items()
            }
        else:
            self.log_freqs = defaultdict(lambda: -10)  # Uniform low score
    
    def suggest(self, word: str, max_distance: int = 2, max_suggestions: int = 5) -> list[str]:
        """
        Get ranked spelling suggestions.
        
        Ranking formula:
            score = -distance + 0.1 * log_frequency + bonuses
        """
        candidates = self._find_candidates(word, max_distance)
        
        scored = []
        for candidate, distance in candidates:
            score = self._compute_score(word, candidate, distance)
            scored.append((candidate, score, distance))
        
        # Sort by score descending, take top k
        scored.sort(key=lambda x: -x[1])
        return [word for word, _, _ in scored[:max_suggestions]]
    
    def _compute_score(self, misspelled: str, suggestion: str, distance: int) -> float:
        """
        Compute ranking score for a suggestion.
        """
        # Base: negative distance (closer = better)
        score = -distance * 10
        
        # Frequency boost
        score += self.log_freqs.get(suggestion, -10)
        
        # First letter match bonus
        if misspelled and suggestion and misspelled[0].lower() == suggestion[0].lower():
            score += 5
        
        # Same length bonus (less disruptive correction)
        if len(misspelled) == len(suggestion):
            score += 2
        
        # Keyboard adjacency bonus (if letters are adjacent keys)
        score += self._keyboard_adjacency_bonus(misspelled, suggestion)
        
        return score
    
    def _keyboard_adjacency_bonus(self, s1: str, s2: str) -> float:
        """
        Bonus for edits that are keyboard-adjacent.
        Common typo pattern: hitting adjacent keys.
        """
        KEYBOARD_ROWS = [
            "qwertyuiop",
            "asdfghjkl",
            "zxcvbnm"
        ]
        
        def are_adjacent(c1: str, c2: str) -> bool:
            c1, c2 = c1.lower(), c2.lower()
            for row in KEYBOARD_ROWS:
                i1, i2 = row.find(c1), row.find(c2)
                if i1 != -1 and i2 != -1 and abs(i1 - i2) == 1:
                    return True
            return False
        
        bonus = 0
        for i in range(min(len(s1), len(s2))):
            if s1[i] != s2[i] and are_adjacent(s1[i], s2[i]):
                bonus += 1
        
        return bonus
    
    def _find_candidates(self, word: str, max_distance: int) -> list[tuple[str, int]]:
        """
        Find all words within max_distance using trie + edit distance.
        (Same algorithm as before)
        """
        candidates = []
        word_len = len(word)
        initial_row = list(range(word_len + 1))
        
        def search(node: dict, prev_row: list[int], depth: int) -> None:
            if self.END in node:
                final_dist = prev_row[-1]
                if final_dist <= max_distance:
                    candidates.append((node[self.END], final_dist))
            
            for char, child in node.items():
                if char == self.END:
                    continue
                
                curr_row = [depth + 1]
                for j in range(1, word_len + 1):
                    if word[j - 1] == char:
                        cost = prev_row[j - 1]
                    else:
                        cost = 1 + min(prev_row[j], curr_row[j - 1], prev_row[j - 1])
                    curr_row.append(cost)
                
                if min(curr_row) <= max_distance:
                    search(child, curr_row, depth + 1)
        
        search(self.trie_root, initial_row, 0)
        return candidates
 
 
# Usage with frequency data:
dictionary = ["the", "tea", "ten", "them", "then", "than"]
frequencies = {"the": 1000000, "tea": 5000, "ten": 8000, "them": 50000, "then": 80000, "than": 60000}
 
checker = AdvancedSpellChecker(dictionary, frequencies)
print(checker.suggest("teh"))  # ['the', 'ten', 'tea'] - 'the' first due to frequency

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

def norvig_corrections(word: str, dictionary: set[str]) -> set[str]:
    """
    Peter Norvig's spell corrector approach.
    
    Generate all edits, filter to dictionary words.
    Extremely fast for small edit distances.
    
    Time: O(54n + 25n²) for edit distance 1, where n = len(word)
          54 = 26 insertions + 26 replacements + 1 deletion + 1 transpose per position
    """
    
    def edits1(w: str) -> set[str]:
        """Generate all strings at edit distance 1 from w."""
        letters = 'abcdefghijklmnopqrstuvwxyz'
        splits = [(w[:i], w[i:]) for i in range(len(w) + 1)]
        
        deletes = [L + R[1:] for L, R in splits if R]
        transposes = [L + R[1] + R[0] + R[2:] for L, R in splits if len(R) > 1]
        replaces = [L + c + R[1:] for L, R in splits if R for c in letters]
        inserts = [L + c + R for L, R in splits for c in letters]
        
        return set(deletes + transposes + replaces + inserts)
    
    def edits2(w: str) -> set[str]:
        """Generate all strings at edit distance 2."""
        return set(e2 for e1 in edits1(w) for e2 in edits1(e1))
    
    # Try in order of increasing edit distance
    candidates = (
        {word} & dictionary or  # Distance 0 (correct spelling)
        edits1(word) & dictionary or  # Distance 1
        edits2(word) & dictionary or  # Distance 2
        {word}  # No corrections found
    )
    
    return candidates
 
 
# Example:
dictionary = {"the", "cat", "car", "card", "tea", "sea"}
print(norvig_corrections("cta", dictionary))  # {'cat'}
print(norvig_corrections("hte", dictionary))  # {'the'}
 
# Why this is fast:
# - edits1("cat") generates ~200 strings
# - Set intersection with dictionary is O(n) 
# - Total: O(200 + D) per query, much faster than O(D × m × n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

def preprocess_for_spell_check(word: str) -> str:
    """
    Normalize word before spell checking.
    """
    if not word:
        return ""
    
    # Lowercase for comparison
    word = word.lower()
    
    # Remove leading/trailing whitespace
    word = word.strip()
    
    # Collapse repeated characters (more than 2)
    # "helllllo" → "hello"
    result = []
    for char in word:
        if len(result) < 2 or not (result[-1] == result[-2] == char):
            result.append(char)
    
    return ''.join(result)
 
 
def should_spell_check(word: str) -> bool:
    """
    Determine if a word should be spell-checked.
    """
    # Skip empty or single-character
    if len(word) <= 1:
        return False
    
    # Skip if contains numbers
    if any(c.isdigit() for c in word):
        return False
    
    # Skip if all uppercase (likely acronym)
    if word.isupper() and len(word) <= 5:
        return False
    
    # Skip URLs and emails
    if '@' in word or '.' in word and '/' in word:
        return False
    
    return True
 
 
# Example preprocessing:
print(preprocess_for_spell_check("Hellooooo"))  # "heloo"
print(preprocess_for_spell_check("TESTING"))    # "testing"
print(should_spell_check("NASA"))               # False (acronym)
print(should_spell_check("test"))               # True