535. Encode and Decode TinyURL

Medium

Description

設計一個 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#

核心思路：本題是開放式設計題，核心是建立長短 URL 之間的雙向映射。可以用自增 ID、Hash、或隨機碼。

需要保證 encode 後的短 URL 是唯一的
decode 時能正確還原
設計取捨：簡短 vs 碰撞風險 vs 可預測性

Approaches#

1: 自增 ID#

概念: 維護一個自增計數器作為短 URL 的 ID，用 HashMap 存儲映射
時間複雜度: O(1) - encode 和 decode 都是 HashMap 操作
空間複雜度: 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: 隨機碼 + 雙向映射#

概念: 生成隨機的 6 位字元碼，用兩個 Map 維護雙向映射，碰撞時重新生成
時間複雜度: O(1) - 平均情況
空間複雜度: 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]!!
    }
}

補充：hashCode 法

使用字串的 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 生成 + 映射存儲
關鍵技巧: 自增 ID 簡單但可預測，隨機碼不可預測但需處理碰撞；實際生產環境還需考慮分散式 ID 生成、過期機制、資料庫持久化等