LeetCode 271. Encode and Decode String

Question

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.

Machine 1 (sender) has the function:

string encode(vector<string> strs) {
  // ... your code
  return encoded_string;
}

Machine 2 (receiver) has the function:

vector<string> decode(string s) {
  //... your code
  return strs;
}

So Machine 1 does:

string encoded_string = encode(strs);

and Machine 2 does:

vector<string> strs2 = decode(encoded_string);

strs2 in Machine 2 should be the same as strs in Machine 1.

Implement the encode and decode methods.

You are not allowed to solve the problem using any serialize methods (such as eval).

Example 1:

Input: dummy_input = ["Hello","World"]
Output: ["Hello","World"]
Explanation:
Machine 1:
Codec encoder = new Codec();
String msg = encoder.encode(strs);
Machine 1 ---msg---> Machine 2

Machine 2:
Codec decoder = new Codec();
String[] strs = decoder.decode(msg);

Example 2:

Input: dummy_input = [""]
Output: [""]

Constraints:

• 1 <= strs.length <= 200
• 0 <= strs[i].length <= 200
• strs[i] contains any possible characters out of 256 valid ASCII characters.

Source: https://leetcode.com/problems/encode-and-decode-strings/

Solution

The best solution is to add a header that represents the length of each string instead of using delimiter. Strings will be concatenated as header-payload-header-....

Note that we call toCharArray method rather than getBytes(). We do not care about the content of payload so that we do not need to encode/decode strings. Also, on some OA platforms, we may need to import desired character set manually.

// encode a 32-bit integer to a char array, according to little endian
// then convert the byte array into a string
private String int2string(int len) {
    char[] bytes = new char[4];
    for (int i = 0; i < 4; i++) {
        bytes[i] = (char) ((len >> (i * 8)) & 0xff);
    }
    return new String(bytes);
}

// decode a 32-bit string to int
private int string2int(String s) {
    char[] bytes = s.toCharArray();
    int len = 0;
    for (int i = 0; i < 4; i++) {
        len += ((int) (bytes[i])) << (i * 8);
    }
    return len;
}

// Encodes a list of strings to a single string.
public String encode(List<String> strs) {
    StringBuilder builder = new StringBuilder();
    for (String str : strs) {
        builder.append(int2string(str.length()));
        builder.append(str);
    }
    return builder.toString();
}

// Decodes a single string to a list of strings.
public List<String> decode(String s) {
    int i = 0;
    List<String> res = new ArrayList<>();
    while (i < s.length()) {
        int strLen = string2int(s.substring(i, i + 4));
        i += 4;
        res.add(s.substring(i, i + strLen));
        i += strLen;
    }
    return res;
}