L8. Encode and Decode Strings (Midium)

Description

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.

Sender has the function:

std::string encode(const std::vector<std::string>& strs){
// ...
	return encoded_string;
}

Receiver has the function:

std::vector<std::string> decode(const std::string& encoded_string){
// ...
	return strs;
}

Solution

看到描述，第一反应是在每一个字符串后面加入额外的特殊字符，如 HTTP 报文中的 CRLF 。但 CR+LF 本来就是回车和换行的意思，但如果这些字符出现在某个字符串中，就会导致解码错误。

一种可行的解决办法是在每个字符串的前面加上该字符串的长度元数据（和 glibc malloc 管理虚拟内存一样），在解码时通过解析长度来找到每个字符串的边界。

用 STL ，我们可以先将题目所给的类型转换成 std::vector<std::pair<int, std::string>> 来存储。