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.

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.

Follow up: Could you write a generalized algorithm to work on any possible set of characters?

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);

Approach

Use length-prefix encoding: encode each string as <length>#<string> and concatenate them all. When decoding, scan digits up to the # to get the length, then read that many characters as the next string. This works for empty strings and arbitrary characters because the length tells us exactly where each segment ends.

Why It Works

Each encoded segment is self-describing: the length prefix uniquely identifies how many characters belong to the next string, regardless of its contents (including #, commas, or newlines). Decoding by reading the length and then slicing that many characters reconstructs the original list in order.

Complexity

• Time: O(n) total characters
• Space: O(n)

Reference Implementation (Python)

class Codec:
    def encode(self, strs: List[str]) -> str:
        pieces = []
        for s in strs:
            pieces.append(f"{len(s)}#{s}")
        return "".join(pieces)

    def decode(self, s: str) -> List[str]:
        res = []
        i = 0
        while i < len(s):
            j = i
            while s[j] != '#':
                j += 1
            length = int(s[i:j])
            j += 1
            res.append(s[j:j + length])
            i = j + length
        return res