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

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.

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