Leetcode # 271. Encode and Decode Strings

https://leetcode.com/problems/encode-and-decode-strings

Solution

Time Complexity: O(len(s))
Space Complexity: O(len(strs))
(The input and output generally do not count towards the space complexity.)

class Codec:
  def encode(self, strs: List[str]) -> str:
    """Encodes a list of strings to a single string.
    """
    encoded = ""
    for s in strs:
      encoded += str(len(s)) + "_" + s
    return encoded

  def decode(self, s: str) -> List[str]:
    """Decodes a single string to a list of strings.
    """
    strs = []
    i = l = 0
    while i < len(s):
      c = s[i]
      o = ord(c)
      if o >= 48 and o <= 57:
        l = l * 10 + (o - 48)
        i += 1
      elif c == "_":
        strs.append(s[i + 1:i + l + 1])
        i += l + 1
        l = 0
    return strs

Other Solutions

1. 用 unicode 字元做為分隔符 (delimiter)
   (strs 的字串只有 ASCII)
2. 用 escape character 做為分隔符
   (/→//，只有我們插入的跳脫字元有單個/)

Time Complexity: O(len(s))
Space Complexity: O(len(strs))
(The input and output generally do not count towards the space complexity.)

Last Updated on 2023/08/16 by A1go