Lintcode Problem 659: Encode and Decode Strings

I stumbled on this exercise while going through the super useful exercise gauntlet from neetcode.io, namely the Arrays & Hashing section. It’s funny that I was expecting to be sent to leetcode.com as it normally happens when clicking on the exercise links, but I was redirected to lintcode.com, which looked like a replica of leetcode… but in Chinese.

As I was submitting the code for review, a prompt came on the screen asking for login details, so I noped out but had already written the code so here goes. I’m not sure my solution works for all test cases since I could only test it on the two input cases in the problem description (let me know in the comments if the code is wrong!),

Description

Design an algorithm to encode a list of strings to a string. The encoded string is then sent over the network and is decoded back to the original list of strings.

Please implement encode and decode

Example1

Input: ["lint","code","love","you"]
Output: ["lint","code","love","you"]
Explanation: One possible encode method is: "lint:;code:;love:;you"

Example2

Input: ["we", "say", ":", "yes"]
Output: ["we", "say", ":", "yes"]
Explanation:
One possible encode method is: "we:;say:;:::;yes"

Python solution Link to heading


# lintcode_659.py

class Solution:
    """
    @param: strs: a list of strings
    @return: encodes a list of strings to a single string.
    """
    def encode(self, strs):
        s = ""
        for word in strs:
            s += f"{word}:;"
        return s

    """
    @param: str: A string
    @return: decodes a single string to a list of strings
    """
    def decode(self, str):
        # return list minus last element, which is ":;"
        return str.split(":;")[:-1]

Complexity analysis Link to heading

  • Time: $ O(n) $ because of the for loop in encode and split.

  • Space: $ O(n) $ since we create the output list with split().



Share on:
LinkedIn