271. Encode and Decode Strings

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

Solution

class Solution:
    def encode(self, strs):
        res = []
        for s in strs:
            res.append(str(len(s)) + "#" + s)
        return "".join(res)

    def decode(self, s):
        res, i = [], 0

        while i < len(s):
            j = i
            while s[j] != "#":
                j += 1
            length = int(s[i:j])
            res.append(s[j + 1 : j + 1 + length])
            i = j + 1 + length
        return res

Time Complexity: O(n)

Space Complexity: O(n)

Explanation

The key idea is to prepend each word with its length and a termination character so that decode is able to process any input.

String concatenation can be made more efficient by emulating java's string builder. i.e. making it a empty list and basically append all the strings. Then simply use "".join(res), or whatever you name the list.