摘要

在分布式系統中，數據的序列化與反序列化是常見的需求，尤其是在網絡傳輸、數據存儲等場景中。LeetCode 第 271 題“字符串的編碼與解碼”要求我們設計一種方法，將字符串數組編碼為單個字符串，并能準確地解碼回原始數組。本文將詳細解析該問題，提供 Swift 語言的解決方案，并結合實際應用場景進行探討。

描述

題目描述：

設計一種方法，將字符串數組編碼為單個字符串，以便在網絡上傳輸。接收方應能解碼該字符串，恢復出原始的字符串數組。

示例：

輸入：[“Hello”,“World”]

輸出：[“Hello”,“World”]

約束條件：

• 1 <= strs.length <= 200

• 0 <= strs[i].length <= 200

• strs[i] 包含任意可能的字符，包括特殊字符。

進階：

你能否設計一個通用的算法，適用于任何可能的字符集？

題解答案

為了解決這個問題，我們需要設計一種編碼方式，使得編碼后的字符串能唯一地表示原始的字符串數組，并且在解碼時能準確地恢復。考慮到字符串中可能包含任何字符，包括我們可能選擇的分隔符，因此直接使用特殊字符作為分隔符可能導致解碼錯誤。一種可靠的方法是采用長度前綴的方式，即在每個字符串前添加其長度和一個分隔符，這樣在解碼時可以根據長度準確地提取每個字符串。

題解代碼分析

以下是使用 Swift 語言實現的編碼和解碼方法：

編碼方法

class Codec {func encode(_ strs: [String]) -> String {var encoded = ""for str in strs {let length = str.countencoded += "\(length)#\(str)"}return encoded}
}

解析：

• 我們遍歷字符串數組中的每個字符串。

• 對于每個字符串，計算其長度，并將長度與字符串本身連接，中間使用 # 作為分隔符。

• 將所有這樣的編碼片段連接起來，形成最終的編碼字符串。

示例：

輸入：[“Hello”, “World”]

編碼過程：

• “Hello” → “5#Hello”

• “World” → “5#World”

最終編碼字符串：“5#Hello5#World”

解碼方法

extension Codec {func decode(_ s: String) -> [String] {var strs = [String]()var i = s.startIndexwhile i < s.endIndex {var j = iwhile s[j] != "#" {j = s.index(after: j)}let length = Int(s[i..<j])!let start = s.index(after: j)let end = s.index(start, offsetBy: length)strs.append(String(s[start..<end]))i = end}return strs}
}

解析：

• 我們使用兩個索引 i 和 j 來遍歷編碼字符串。

• 首先，找到下一個 # 分隔符，提取出長度信息。

• 然后，根據長度提取出對應的字符串。

• 將提取出的字符串添加到結果數組中，繼續處理下一個編碼片段。

示例：

編碼字符串：“5#Hello5#World”

解碼過程：

• 提取長度 5，字符串 “Hello”

• 提取長度 5，字符串 “World”

最終結果：[“Hello”, “World”]

示例測試及結果

我們可以通過以下示例來驗證編碼和解碼方法的正確性：

let codec = Codec()
let original = ["Hello", "World", "Swift", "LeetCode"]
let encoded = codec.encode(original)
print("Encoded: \(encoded)")
let decoded = codec.decode(encoded)
print("Decoded: \(decoded)")

輸出：

Encoded: 5#Hello5#World5#Swift8#LeetCode
Decoded: ["Hello", "World", "Swift", "LeetCode"]

可以看到，解碼后的結果與原始數組完全一致，驗證了方法的正確性。

時間復雜度

• 編碼方法：

  • 我們遍歷字符串數組中的每個字符串，計算其長度并進行字符串連接。

  • 假設字符串數組中有 n 個字符串，總字符數為 k，則時間復雜度為 O(k)。

• 解碼方法：

  • 我們遍歷編碼字符串，提取每個字符串的長度和內容。

  • 同樣，時間復雜度為 O(k)。

空間復雜度

• 編碼方法：

  • 我們構建了一個新的字符串，長度為原始字符串總長度加上長度前綴和分隔符的長度。

  • 因此，空間復雜度為 O(k)。

• 解碼方法：

  • 我們構建了一個新的字符串數組，包含原始的所有字符串。

  • 因此，空間復雜度為 O(k)。

總結

通過在每個字符串前添加其長度和一個分隔符，我們可以可靠地將字符串數組編碼為單個字符串，并能準確地解碼回原始數組。這種方法避免了使用特殊字符作為分隔符可能帶來的問題，具有較高的可靠性和通用性。在實際應用中，如網絡傳輸、數據存儲等場景，這種編碼方式具有重要的實用價值。

在更復雜的系統中，我們可能需要處理更復雜的數據結構，如嵌套的數組、字典等。此時，可以考慮使用更通用的序列化方法，如 JSON、XML 等，或者使用專門的序列化框架，如 Protocol Buffers、Thrift 等，以滿足更高的性能和可擴展性需求。