0271.Encode and Decode Strings

• Link: 271. Encode and Decode Strings - Medium
• Track: NeetCode150

Question

• Example 1:
  • Input: dummy_input = ["Hello","World"]
  • Output: ["Hello","World"]
• Explanation:
  • Machine 1:
    • Codec encoder = new Codec();
    • String msg = encoder.encode(strs);
    • Machine 1 ---msg-⇒ Machine 2
  • Machine 2:
    • Codec decoder = new Codec();
    • String[] strs = decoder.decode(msg);

Restate the problem

• Given a list of string
• Build encode function, convert list of string to a single string
• Build decode function, convert a single string to list of string
• Requirements:
  • Strings may contain uppercase/lowercase letters, digits, symbols, spaces

Edge Case

• support ["1", "2", "3"]
• support ["#", "2L", "o"]

---

Method	Approach	Time Complexity	Space Complexity
Method 1 ⭐	Length-prefix encoding	$O(n)$	$O(n)$

Method 1

Approach

• Encode each string as: <length>#<string>
• Encoding:
  • For each word word in strs:
    • Compute length = len(word)
    • Append "{length}#{w}" to an array parts
    • Return "".join(parts) (avoids O(N^2))
• Decoding:
  • While idx within the string:
    • Move sign to find #
    • Before sign is length, convert s[length_start: delimiter] to length
    • Extract string lenght, append into res
    • Move idx forward by length

Complexity

• Time Complexity:
  • encode: $O(n)$
  • decode: $O(n)$
• Space Complexity:
  • encode: $O(n)$
  • decode: $O(n)$

Code

class Codec:
    def encode(self, strs: List[str]) -> str:
        res = []
        for word in strs:
            length = len(word)
            # res += str(length) + "#" + word # cause O(n^2)
            res.append(f"{length}#{word}")
        return "".join(res)
 
    def decode(self, s: str) -> List[str]:
        res = []
        idx = 0
        while idx < len(s):
            length_start = idx
 
            while s[idx] != "#":
                idx += 1
 
            delimiter = idx
            word_length = int(s[length_start: delimiter])
            
            word_start = delimiter + 1
            word_end = word_start + word_length
 
            res.append(s[word_start: word_end])
 
            idx = word_end
        
        return res

---

Common mistake