實戰：自動拼寫檢查

Vibe Prompt

「幫我用 FastAPI 建立一個拼寫檢查 API：輸入單字，回傳最相似的 5 個正確拼寫。」

# spell_checker.py
from fastapi import FastAPI
from pydantic import BaseModel

app = FastAPI(title="拼寫檢查 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", "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)

擴充功能

| 功能 | 實作方式 | |------|---------| | 多語言支援 | 加入 zh-TW、ja 字典 | | 自動學習 | 追蹤未知單字，標記供審核 | | 語音比對 | 加入 Soundex/Metaphone 作備援 | | 批次檢查 | 接受單字陣列 | | 上下文感知 | 使用 n-gram 語言模型排序建議 |

總結

| 面向 | 詳情 | |------|------| | 演算法 | Levenshtein DP (O(m×n)/次比較) | | API 框架 | FastAPI + Pydantic 驗證 | | 字典 | 記憶體列表（生產環境可達 50K+ 單字） | | 優化 | 大規模字典可使用 BK-tree 或 trie 加速 | | 部署 | uvicorn spell_check:app --host 0.0.0.0 --port 8000 |

DP 課程完成！🎉

✅ DP 核心（遞迴 + 表格法）
✅ 0/1 背包問題
✅ 最長共同子序列（LCS）
✅ 編輯距離（Levenshtein）
✅ 拼寫檢查 API
✅ 計算量分析（空間/時間優化n- ✅ 編輯距離（Levenshtein）\n- ✅ 拼寫檢查 API\n- ✅ 計算量分析（空間/時間優化）"}]}

常見問題與解決方案

| 問題 | 原因 | 解法 | |------|------|------| | 結果不如預期 | 參數設定不當 | 檢查預設值與邊界條件 | | 執行速度慢 | 演算法效率低 | 考慮使用更高效的資料結構 | | 記憶體不足 | 資料量過大 | 使用批次處理或串流方式 | | 難以除錯 | 缺乏日誌 | 加入詳細的 log 輸出 |

效能考量

When working with large datasets or complex computations:

時間複雜度: Analyze and optimize Big O
空間複雜度: Balance memory vs speed
Caching: Store computed results to avoid recalculation
Parallelism: Use multi-threading for independent tasks
Profiling: Measure before optimizing - use profilers

Real-World Application

This concept is widely used in:

Web development (routing, authentication)
Data science (feature engineering, model training)
Game development (pathfinding, physics)
Mobile apps (state management, caching)

拼寫檢查系統：編輯距離的實戰應用

編輯距離（Levenshtein Distance）計算把一個字串轉換成另一個字串需要的最少操作次數——插入、刪除、取代。這是一個經典的 DP 問題。

編輯距離的 DP 表格

     ''  s  i  t  t  i  n  g
''   0  1  2  3  4  5  6  7
k    1  1  2  3  4  5  6  7
i    2  2  1  2  3  4  5  6
t    3  3  2  1  2  3  4  5
te   4  4  3  2  2  3  4  5
ten  5  5  4  3  3  3  3  4

sitting → kitten 的編輯距離是 4。

為什麼這很有用？

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]

# 使用
spell_check("appple", ["apple", "banana", "application", "appetite"])
# 回傳：["apple", "appetite", "application"]

課程總結

這堂 DP 課程你從遞迴+記憶化、0/1 背包、LCS、編輯距離到拼寫檢查 API——現在你看到一個問題時，可以判斷它是否適合用 DP 解，並且知道該如何定義狀態和轉移。