解題說明
Encode and Decode TinyURL
題目描述： 設計一個 TinyURL 系統的編碼（encode）和解碼（decode）方法。encode 將長 URL 轉換為短 URL，decode 將短 URL 還原為長 URL。
解題思路： 使用隨機生成短碼 + 雜湊表雙向映射：
- encode：為每個長 URL 生成一個 6 位的隨機短碼（從
[a-zA-Z0-9]中取）。用雜湊表codeToUrl儲存短碼到長 URL 的映射，urlToCode儲存長 URL 到短碼的映射（避免同一 URL 產生不同短碼）。 - decode：從短 URL 中提取短碼，查找
codeToUrl回傳原始長 URL。
碰撞處理：若生成的短碼已存在（映射到不同 URL），重新生成。62^6 約 568 億種組合，碰撞概率極低。
C++ 解法
複雜度分析
時間複雜度：encode O(1) 攤銷（碰撞概率極低），decode O(1) — 雜湊表查找。
空間複雜度：O(n) — n 為已編碼的 URL 數量，兩個雜湊表各存 n 個映射。
虛擬碼
1. Maintain two maps: codeToUrl, urlToCode 2. encode(longUrl): a. If longUrl already encoded, return existing short URL b. Generate random 6-char code from [a-zA-Z0-9] c. While code collides, regenerate d. Store code -> longUrl and longUrl -> code e. Return prefix + code 3. decode(shortUrl): a. Extract code from shortUrl b. Return codeToUrl[code]
其他解法
自增 ID 法：用全域遞增計數器作為短碼（轉成 base62 字串）。保證無碰撞，但 URL 是可預測的（安全性較差，可被遍歷）。時間 O(1)，空間 O(n)。在實際系統中常配合分散式 ID 生成器（如 Snowflake）使用。
雜湊法（MD5/SHA256）：對長 URL 做雜湊，取前 6-8 字元作為短碼。碰撞時追加序號或重新雜湊。確定性（同一 URL 永遠映射到同一短碼），但碰撞處理較複雜。適合需要冪等性的場景。
延伸思考
- 若系統需要支援數十億 URL，短碼長度 6 是否足夠？如何估算需要的短碼長度？
- 在分散式系統中，如何避免多個伺服器同時生成相同的隨機短碼？
- 如何為 TinyURL 添加過期機制？需要哪些額外的資料結構？