Problem

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.

Note: Because the string may contain any of the 256 legal ASCII characters, your algorithm must be able to handle any character that may appear

Do not rely on any libraries, the purpose of this problem is to implement the “encode” and “decode” algorithms on your own

Examples

Example1

1
2
3
4

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

Example2

1
2
3
4

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

Solution

There are multiple ways we can encode string. For eg. using special char like # to separate the strings while encoding. But the problem is what if the special char is part of string. Then it will be a problem.

What we can do is use special char like # but also append or prepend number of chars of string we have. For eg. we -> we#2.

Video explanation

Here is the video explaining below methods in detail. Please check it out:

Method 1 - Use Special Char and Length of Word

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

public class Codec {

	// Encodes a list of strings to a single string.
	public String encode(List<String> strs) {
		StringBuilder sb = new StringBuilder();

		for (String str: strs) {
			sb.append(str.length()).append('/').append(str);
		}

		return sb.toString();
	}

	// Decodes a single string to a list of strings.
	public List<String> decode(String s) {
		List<String> ans = new ArrayList<>();
		int i = 0;

		while (i < s.length()) {
			int slash = s.indexOf('/', i);
			int size = Integer.valueOf(s.substring(i, slash));
			ans.add(s.substring(slash + 1, slash + size + 1));
			i = slash + size + 1;
		}

	}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

    """  
    @param: strs: a list of strings  
    @return: encodes a list of strings to a single string.  
    """  
    def encode(self, strs):  
        res = ''  
        for s in strs:  
            encoded = str(len(s)) + '/' + s  
            res += encoded  
        return res    """  
    @param: str: A string  
    @return: dcodes a single string to a list of strings  
    """  
    def decode(self, str):  
        res, i = [], 0  
        while i < len(str):  
            # For example, 12/abc  
            e = i  
            while e < len(str) and str[e] != '/':  
                e += 1  
            size = int(str[i:e])  
            word = str[e + 1, e + 1 + size]  
            i = e + 1 + size  
            res.append(word)  
        return res