Encode and decode strings#

Levels: level-4

Data structures: string

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.

Note:

The string may contain any possible characters out of 256 valid ascii characters. Your algorithm should be generalized enough to work on any possible characters.
Do not use class member/global/static variables to store states. Your encode and decode algorithms should be stateless.
Do not rely on any library method such as eval or serialize methods. You should implement your own encode/decode algorithm.

Python Solution#

 1from functools import reduce
 2
 3
 4class Codec(object):
 5    def encode(self, strs):
 6        """
 7        Encodes a list of strings to a single string.
 8
 9        Algorithm: Length info
10
11        :type strs: List[str]
12        :rtype: str
13        """
14        strs = list(map(lambda x: str(len(x)) + "/" + x, strs))
15        return reduce(lambda x, y: x + y, strs, "")  # i.e. "".join(strs)
16
17    def decode(self, s):
18        """
19        Decodes a single string to a list of strings.
20
21        :type s: str
22        :rtype: List[str]
23        """
24        strs = []
25        i = 0
26        while i < len(s):
27            j = s.index("/", i)
28            l = int(s[i:j])
29            strs.append(s[j + 1:j + 1 + l])
30            i = j + 1 + l
31
32        return strs
33
34
35class CodecMethod2(object):
36    def encode(self, strs):
37        """
38        Encodes a list of strings to a single string.
39
40        Algorithm: Escape
41
42        :type strs: List[str]
43        :rtype: str
44        """
45        strs = list(map(lambda x: x.replace("\n", "\n\n") + "_\n_", strs))
46        return reduce(lambda x, y: x + y, strs, "")
47
48    def decode(self, s):
49        """
50        Decodes a single string to a list of strings.
51
52        :type s: str
53        :rtype: List[str]
54        """
55        strs = s.split("_\n_")
56        strs = strs[:-1]  # clear the trailing delimiter
57        return list(map(lambda x: x.replace("\n\n", "\n"), strs))