【LeetCode最详尽解答】271_编码和解码字符串 Encode-and-Decode-Strings

欢迎收藏Star我的Machine Learning Blog:https://github.com/purepisces/Wenqing-Machine_Learning_Blog。如果收藏star, 有问题可以随时与我交流, 谢谢大家！

链接：

• 271_编码和解码字符串

直觉

我观看了 Neetnode 关于这个问题的视频。如果我们只是将 ['hello', 'world'] 编码为 'helloworld'，然后解码回来，我们将不知道在哪里分隔这些单词。我们可以考虑使用特殊字符来分隔它们。例如，我们可以添加 #，使其变为 'hello#world'。

然而，如果单词是 ['hello', 'wo#rld']，编码后会变成 'hello#wo#rld'，解码回来会得到 ['hello', 'wo', 'rld']。这意味着仅使用特殊字符并不是一种可靠的方法。

相反，我们应该将每个单词的长度集成到编码信息中。例如，将 ['hello', 'world'] 编码为 '5hello5world' 可能有效，但如果输入是 ['1hello', 'world']，它会编码为 '61hello5world'，使得第一个单词看起来长度为 61。因此，仅添加整数或特殊字符是不够的。

更好的方法是将长度信息与特殊字符结合起来。例如，将 ['hello', 'world'] 编码为 '5#hello5#world'。

在解码过程中，我们使用两个指针，i 和 j。指针 i 用于遍历编码字符串，而指针 j 用于定位将每个单词的长度与单词本身分开的 # 字符。这帮助我们确定每个单词的长度并相应地提取单词。

方法

要编码一个字符串列表，我们将每个字符串与其长度和一个特殊字符 # 连接在一起。这样，在解码过程中，我们可以轻松识别每个字符串的长度并相应地提取它。

编码：

1. 初始化一个空的结果字符串。
2. 对于输入列表中的每个字符串，将其长度、一个 # 字符和字符串本身附加到结果字符串中。

解码：

1. 初始化一个空的结果列表。
2. 使用两个指针，i 和 j：
   • i 遍历编码字符串。
   • j 定位 # 字符以确定每个单词的长度。
3. 迭代编码字符串，使用 # 字符作为分隔符来识别长度和相应的子字符串。
4. 根据它们的长度提取子字符串并将它们附加到结果列表中。

复杂度

• 时间复杂度：
  $$O(N)$$
  • 其中 $N$ 是输入列表中所有字符串的总长度。我们在编码和解码过程中分别遍历每个字符一次。
• 空间复杂度：
  $$O(N)$$
  • 其中 $N$ 是输入列表中所有字符串的总长度。我们在解码过程中使用额外的空间存储编码字符串和结果列表。

代码

class Solution:

    def encode(self, strs: List[str]) -> str:
        res = ''
        for s in strs:
            res += str(len(s)) + '#' + s
        print(res)
        return res

    def decode(self, s: str) -> List[str]:
        res = []
        i = 0
        while i < len(s):
            j = i
            while s[j] != '#':
                j += 1
            length = int(s[i:j])
            i = j + 1
            j = i + length
            res.append(s[i:j])
            i = j
        return res