Encode & Decode Strings

Problem Summary

(Write in your own words, not copied from LeetCode. This forces comprehension.)

• You're given a list of words, write two functions:
  • encode - that encodes all words into a single string
  • decode - that decodes the same string into a list of words

Key Observations

(Patterns, constraints, or hints in the problem statement.)

• Length of word could be in two digits
• Any delimiter you choose can be part of the string itself
• Delimiter needs to be length of word + delimiter

Main Concepts Used

(Mark the CS concepts or algorithms used.)

• Strings
• Array

Time & Space Complexity

• Time: $O(n)$ → Reason: Going through each character once
• Space: $O(n)$ → Reason: Storing once

Code

class Solution:
    # 4%neet10%aaabbbcccd
    # len(word) + delimiter

    delimiter = "$"

    def encode(self, strs: List[str]) -> str:
        result = []
        for word in strs:
            result.append(str(len(word)))
            result.append(self.delimiter)
            result.append(word)
        return "".join(result)

    def decode(self, s: str) -> List[str]:
        result = []
        i = 0
        number = []
        while i < len(s):
            character = s[i]
            if character == self.delimiter:
                numOfChars = int("".join(number))
                startOfWord = i + 1
                endOfWord = startOfWord + numOfChars
                word = s[startOfWord:endOfWord]
                i = endOfWord
                number.clear()
                result.append(word)
            else:
                number.append(character)
                i += 1
        return result

Common Mistakes / Things I Got Stuck On

• number was stored inside the while loop which cleared it every iteration
• len(word) needs to be converted to a string
• Ensure indexing is correct