⚡Encode and Decode Strings

Encode and Decode Strings

• Difficulty: Medium
• Company: LeetCode75
• Optimization: Yes
• Review: January 8, 2025
• Select: String
• Solved: Yes
• Tried: 2

My Answer: Delimiter-Based Encoding

class Solution:

    def encode(self, strs: List[str]) -> str:
        answer = '!@#$%123456789'.join(strs)
        if len(strs) == 0:
            answer = "I am empty"
        return answer

    def decode(self, s: str) -> List[str]:
        answer = s.split('!@#$%123456789')
        if s == "I am empty":
            answer = []
        return answer

• Complexity
  • $N$ : The number of elements in the strs list (i.e., the number of elements).
  • $K$ : The average number of character in each element.
  • M: The length of the string s
• Time: $O(N×L)$
  • encode: $O(N×L)$
    • join(strs): Combines N elements in the list, adding the length L of each string to create the final encoded string → $O(N×L)$
  • decode: $O(M)$
    • split('delimiter'): The split method iterates through the string s to find the delimiter, resulting in $O(M)$
• Space:
  • encode: $O(N×L)$
    • answer: The string generated by the join method combines all strings in the strs list, so it requires space proportional to $O(N×L)$
  • decode: $O(M)$
    • answer: The list created by the split method occupies memory proportional to the length of the string s, which is $O(M)$

Reflection

• Exploring various solutions and clearly communicating them
• Stating the runtime and space complexity (the pros and cons) of each solution)
• Translating ideas into code
• Debugging your code

Best Answer

1. Length-Based Encoding

class Codec:
    def encode(self, strs):
        text = ""
        for str in strs:
            text += f"{len(str)}:{str}"
        return text

    def decode(self, s):
        ls, start = [], 0 #ls: List for saving original list
                          #start: Variable can track the current location
        #While loop: Iterate all character of s
        while start < len(s):

            mid = s.find(":", start)#mid: find method check ":" from start(0) to first ":"
            length = int(s[start:mid]) #length: int from start to mid 
            ls.append(s[mid + 1 : mid + 1 + length])#Append the element -> mid+1(: 다음) 부터 mid+1+length()
            start = mid + 1 + length
        return ls

myCodec = Codec()

myCodec.decode(myCodec.encode(['Hello','World']))

• Complexity
  • $N$ : The number of elements in the strs list (i.e., the number of elements).
  • $K$ : The average number of character in each element.
  • M: The length of the string s
• Time: $O(N*L)$
  • Encoding:
    • Count each character of each element(string str) and concatenate them with the length → $O(L)$
    • Repeat the above step for every element in the strs list → $O(N)$
  • Decoding
    • Find the position of the delimiter (":") for each encoded segment → $O(M)$
    • Slice each segment based on its length and append to the result → $O(L)$
    • Repeat the above step for all elements in the encoded string → $O(N)$
• Space: $O(N*L)$
  • Encoding:
    • Store the encoded string, which contains all elements in the “length:string” format → $O(N×L)$
  • Decoding:
    • Store the decoded list, which has the same size as the input string list → $O(N×L)$
    • Use additional variables like length, mid, and start, but they consume constant space → $O(1)$