Encode and Decode Strings

MediumStrings

Design encode and decode so that a list of strings can be serialized to one string and recovered exactly, even with any characters.

Open problem

Constraints

0 <= strs.length <= 200
Any ASCII characters allowed

Length-prefix framing

Time O(total length)Space O(total length)

Prefix each string with its length and a delimiter, like '5#hello'. Decoding reads the length up to the delimiter, then slices exactly that many characters, which is unambiguous regardless of content.

#include <bits/stdc++.h>
using namespace std;

string encode(vector<string>& strs) {
    string res;
    for (string& s : strs) res += to_string(s.size()) + "#" + s;
    return res;
}

vector<string> decode(string s) {
    vector<string> res;
    int i = 0, n = s.size();
    while (i < n) {
        int j = i;
        while (s[j] != '#') j++;
        int len = stoi(s.substr(i, j - i));
        res.push_back(s.substr(j + 1, len));
        i = j + 1 + len;
    }
    return res;
}