解題說明
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 添加過期機制?需要哪些額外的資料結構?