271. Encode and Decode Strings

Medium

Description

設計演算法將字串列表編碼為單一字串，並能正確解碼還原。字串可包含任意字元（包括分隔符號）。此為 LeetCode Premium 題，NeetCode 等平台提供免費版。

Example:

Input: [“hello”,“world”] Output: [“hello”,“world”] （經過 encode -> decode 後還原）

Intuition#

核心思路：不能用簡單分隔符（字串可能包含任意字元），改用「長度前綴」方式——每個字串前加上其長度和固定分隔符。

用任何單一字元作分隔符都會失敗，因為字串本身可能包含該字元
Escape character 方式可行但解碼複雜
長度前綴法：len#string，因為長度是數字且 # 只在長度後出現一次，可以無歧義地解析

Approaches#

1: Escaping#

概念: 選擇一個特殊字元作分隔符，對字串中出現的該字元進行轉義（如 / -> //，用 /: 做分隔）
時間複雜度: O(n) - n 為所有字串的總長度
空間複雜度: O(n) - 編碼後的字串

class Codec {
    fun encode(strs: List<String>): String {
        val sb = StringBuilder()
        for (s in strs) {
            for (c in s) {
                if (c == '/') sb.append("//")
                else sb.append(c)
            }
            sb.append("/:")
        }
        return sb.toString()
    }

    fun decode(s: String): List<String> {
        val result = mutableListOf<String>()
        val sb = StringBuilder()
        var i = 0
        while (i < s.length) {
            if (i + 1 < s.length && s[i] == '/' && s[i + 1] == ':') {
                result.add(sb.toString())
                sb.clear()
                i += 2
            } else if (i + 1 < s.length && s[i] == '/' && s[i + 1] == '/') {
                sb.append('/')
                i += 2
            } else {
                sb.append(s[i])
                i++
            }
        }
        return result
    }
}

⭐2: Length Prefix#

概念: 每個字串前加上 長度#，解碼時先讀取數字直到遇到 #，再根據長度讀取對應字元數
時間複雜度: O(n) - n 為所有字串的總長度
空間複雜度: O(n) - 編碼後的字串

class Codec {
    fun encode(strs: List<String>): String {
        val sb = StringBuilder()
        for (s in strs) {
            sb.append(s.length).append('#').append(s)
        }
        return sb.toString()
    }

    fun decode(s: String): List<String> {
        val result = mutableListOf<String>()
        var i = 0
        while (i < s.length) {
            val j = s.indexOf('#', i)
            val len = s.substring(i, j).toInt()
            result.add(s.substring(j + 1, j + 1 + len))
            i = j + 1 + len
        }
        return result
    }
}

長度前綴法的關鍵：解碼時是靠長度來決定字串的邊界，而不是靠搜尋分隔符。所以即使字串內容包含 # 或數字也完全不受影響。

🔑 Takeaways#

Pattern: 序列化 / 反序列化 -> 長度前綴（Length-Delimited）是最可靠的方式
關鍵技巧: 長度#內容 的編碼方式在很多通訊協定中被使用（如 HTTP chunked encoding）。面試時這類設計題重點在於想清楚 edge case（空字串、含特殊字元的字串）