title: "Hands-On: Auto Spell Check System" description: "Integrate DP to build an auto spell check system, wrapped as an API with Vibe Coding." order: 5
Hands-On: Auto Spell Check System
Vibe Prompt
"Use FastAPI to build a spell check API: input a word, return the 5 most similar correct spellings."
from fastapi import FastAPI
from pydantic import BaseModel
app = FastAPI(title="Spell Check API")
def edit_distance(s1, s2):
m, n = len(s1), len(s2)
dp = [[0]*(n+1) for _ in range(m+1)]
for i in range(m+1): dp[i][0] = i
for j in range(n+1): dp[0][j] = j
for i in range(1, m+1):
for j in range(1, n+1):
if s1[i-1] == s2[j-1]:
dp[i][j] = dp[i-1][j-1]
else:
dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])
return dp[m][n]
DICTIONARY = ["coding", "vibe", "tutor", "python", "algorithm",
"react", "next", "docker", "kubernetes", "fastapi", "tailwind"]
class SpellRequest(BaseModel):
word: str
top_k: int = 5
class SpellResponse(BaseModel):
original: str
suggestions: list
@app.post("/spell-check", response_model=SpellResponse)
def spell_check(req: SpellRequest):
scored = [(w, edit_distance(req.word, w)) for w in DICTIONARY]
scored.sort(key=lambda x: x[1])
suggestions = [{"word": w, "distance": d} for w, d in scored[:req.top_k]]
return SpellResponse(original=req.word, suggestions=suggestions)
if __name__ == "__main__":
import uvicorn
uvicorn.run(app, host="0.0.0.0", port=8000)
Extension Features
| Feature | Implementation | |---------|----------------| | Multi-language Support | Add zh-TW, ja dictionaries | | Auto Learning | Track unknown words, flag for review | | Phonetic Matching | Add Soundex/Metaphone as fallback | | Batch Check | Accept word arrays | | Context Awareness | Use n-gram language model to rank suggestions |
Summary
| Aspect | Detail | |--------|--------| | Algorithm | Levenshtein DP (O(m x n) per comparison) | | API Framework | FastAPI + Pydantic validation | | Dictionary | In-memory list (production: 50K+ words) | | Optimization | BK-tree or trie for large dictionaries | | Deployment | uvicorn spell_check:app --host 0.0.0.0 --port 8000 |
Spell Check: Real-World Edit Distance
Edit Distance calculates minimum operations to transform one string to another. A classic DP problem.
Why It Matters
def spell_check(word: str, dictionary: list[str], max_results: int = 5):
distances = []
for candidate in dictionary:
dist = levenshtein_distance(word, candidate)
distances.append((candidate, dist))
distances.sort(key=lambda x: x[1])
return distances[:max_results]
Course Summary
This DP course covered recursion+memoization, 0/1 Knapsack, LCS, Edit Distance, and Spell Check API - you can now determine if DP applies to a problem and know how to define states and transitions.
How the Spell Check API Works
The API receives a word, computes edit distance against a dictionary of known words, and returns the closest matches ranked by similarity.
Request: GET /spell-check?word=kol
Response: {
"original": "kol",
"suggestions": [
{"word": "cool", "distance": 1, "similarity": 0.75},
{"word": "kool", "distance": 1, "similarity": 0.75},
{"word": "coal", "distance": 1, "similarity": 0.75}
]
}
FastAPI Implementation
from fastapi import FastAPI, Query
from typing import List
import heapq
app = FastAPI(title="Spell Check API", version="1.0.0")
# Dictionary of known words (in production, load from a file)
DICTIONARY = [
"cool", "cold", "coal", "kool", "cole", "coral", "crawl",
"school", "scholar", "kohl", "koala", "call", "cell", "cull",
"hello", "help", "helm", "held", "hell", "half", "halt",
"world", "word", "worm", "worn", "work", "wore", "cord",
"algorithm", "dynamic", "programming", "python", "fastapi",
"kitten", "sitting", "spelling", "dictionary", "suggestion",
"distance", "similarity", "levenstein", "levenshtein", "edit"
]
def edit_distance(s1: str, s2: str) -> int:
"""Compute minimum edit distance between two strings."""
m, n = len(s1), len(s2)
if m < n:
s1, s2 = s2, s1
m, n = n, m
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):
cost = 0 if s1[i - 1] == s2[j - 1] else 1
curr[j] = min(
prev[j] + 1,
curr[j - 1] + 1,
prev[j - 1] + cost
)
prev, curr = curr, prev
return prev[n]
@app.get("/spell-check", summary="Check spelling and get suggestions")
async def spell_check(
word: str = Query(..., min_length=1, max_length=50),
max_results: int = Query(5, ge=1, le=20),
max_distance: int = Query(3, ge=1, le=5)
):
"""
Check if a word is spelled correctly.
If not, suggest the closest matches from the dictionary.
"""
word_lower = word.lower()
# Check if the word is already in the dictionary
if word_lower in DICTIONARY:
return {
"original": word,
"correct": True,
"message": "Spelling is correct."
}
# Compute edit distance against all dictionary words
candidates = []
for dict_word in DICTIONARY:
dist = edit_distance(word_lower, dict_word)
if dist <= max_distance:
similarity = 1.0 - (dist / max(len(word_lower), len(dict_word)))
# Use negative distance as priority queue key (heap is min-heap)
candidates.append((dist, similarity, dict_word))
# Sort by distance (ascending), then by similarity (descending)
candidates.sort(key=lambda x: (x[0], -x[1]))
suggestions = [
{
"word": c[2],
"distance": c[0],
"similarity": round(c[1], 2)
}
for c in candidates[:max_results]
]
return {
"original": word,
"correct": False,
"suggestions": suggestions,
"total_candidates": len(candidates)
}
Running the API
# Install dependencies
pip install fastapi uvicorn
# Run the server
uvicorn main:app --reload --port 8000
# Test
curl "http://localhost:8000/spell-check?word=kol"
curl "http://localhost:8000/spell-check?word=helo"
curl "http://localhost:8000/spell-check?word=algoritm"
Performance Optimization
For large dictionaries (100k+ words), edit distance against every word is slow.
| Strategy | Speedup | Complexity | |----------|---------|------------| | BK-Tree (Burkhard-Keller Tree) | 10-100x | O(log n) average per query | | Symmetric Delete | 100-1000x | Precompute deletions up to max distance | | Trie + DP pruning | 5-10x | Prune branches when partial distance exceeds max | | Character n-gram indexing | 10-50x | Pre-filter by shared n-grams |
BK-Tree Implementation
class BKTree:
"""BK-tree for fast spelling correction queries."""
def __init__(self, words):
self.tree = None
for word in words:
self.insert(word)
def insert(self, word):
if self.tree is None:
self.tree = (word, {})
return
node = self.tree
while True:
dist = edit_distance(word, node[0])
if dist == 0:
return # word already in tree
if dist not in node[1]:
node[1][dist] = (word, {})
return
node = node[1][dist]
def query(self, word, max_dist):
"""Find all words within max_dist of the query word."""
if self.tree is None:
return []
results = []
stack = [self.tree]
while stack:
node_word, children = stack.pop()
dist = edit_distance(word, node_word)
if dist <= max_dist:
results.append((node_word, dist))
# Only visit children within the distance range
for child_dist, child_node in children.items():
if abs(child_dist - dist) <= max_dist:
stack.append(child_node)
results.sort(key=lambda x: x[1])
return results
# Build tree from dictionary
bk_tree = BKTree(DICTIONARY)
results = bk_tree.query("kol", 2)
print(f"Suggestions for 'kol': {results}")
Summary
The Spell Check API wraps edit distance into a practical FastAPI service. It checks words against a dictionary and returns ranked suggestions. For production with large dictionaries, use a BK-tree for fast approximate search.
Key takeaways:
- FastAPI endpoint accepts a word and returns spelling suggestions
- Edit distance computes similarity against every dictionary word
- Results are sorted by distance (ascending) and similarity (descending)
- For large dictionaries, BK-tree reduces query time from O(n) to O(log n)
- Symmetric delete precomputation offers 100-1000x speedup
- Always lowercase both query and dictionary for case-insensitive matching
- Set max_distance to limit suggestions to reasonable corrections
- The space-optimized edit distance uses O(min(m,n)) memory
What's Next: Algorithm โ Greedy Algorithms
The next course covers greedy algorithms โ Kruskal, Prim, Huffman coding, and set cover.