設計一個 TinyURL 的加密與解密方法。
encode將長 URL 轉為短 URL，decode將短 URL 還原為長 URL。
Example:
Input: url = “https://leetcode.com/problems/design-tinyurl” Output: “https://leetcode.com/problems/design-tinyurl”（encode 後再 decode 回原 URL）
Intuition
TIP
核心思路：本題是開放式設計題，核心是建立長短 URL 之間的雙向映射。可以用自增 ID、Hash、或隨機碼。
- 需要保證 encode 後的短 URL 是唯一的
- decode 時能正確還原
- 設計取捨：簡短 vs 碰撞風險 vs 可預測性
Approaches
1. Auto-increment ID — O(1) / O(n)
- Idea: 維護一個自增計數器作為短 URL 的 ID，用 HashMap 存儲映射
- Time:
O(1)- encode 和 decode 都是 HashMap 操作 - Space:
O(n)- n 為已編碼的 URL 數量
class Codec() {
private val map = HashMap<String, String>()
private var id = 0
fun encode(longUrl: String): String {
val shortUrl = "http://tinyurl.com/${id++}"
map[shortUrl] = longUrl
return shortUrl
}
fun decode(shortUrl: String): String {
return map[shortUrl]!!
}
}⭐ 2. Random Code + Bidirectional Map — O(1) / O(n)
- Idea: 生成隨機的 6 位字元碼，用兩個 Map 維護雙向映射，碰撞時重新生成
- Time:
O(1)- 平均情況 - Space:
O(n)
class Codec() {
private val longToShort = HashMap<String, String>()
private val shortToLong = HashMap<String, String>()
private val chars = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789"
private val base = "http://tinyurl.com/"
fun encode(longUrl: String): String {
if (longToShort.containsKey(longUrl)) {
return longToShort[longUrl]!!
}
var code: String
do {
code = (1..6).map { chars.random() }.joinToString("")
} while (shortToLong.containsKey(base + code))
val shortUrl = base + code
longToShort[longUrl] = shortUrl
shortToLong[shortUrl] = longUrl
return shortUrl
}
fun decode(shortUrl: String): String {
return shortToLong[shortUrl]!!
}
}Note: hashCode Approach
使用字串的 hashCode 作為短碼，簡單但有碰撞風險。
class Codec() {
private val map = HashMap<Int, String>()
fun encode(longUrl: String): String {
val hash = longUrl.hashCode()
map[hash] = longUrl
return "http://tinyurl.com/$hash"
}
fun decode(shortUrl: String): String {
val hash = shortUrl.substringAfterLast("/").toInt()
return map[hash]!!
}
}🔑 Takeaways
- Pattern: 系統設計入門題——URL 短縮服務的核心是 ID 生成 + 映射存儲
- Key trick: 自增 ID 簡單但可預測，隨機碼不可預測但需處理碰撞；實際生產環境還需考慮分散式 ID 生成、過期機制、資料庫持久化等