Notes

271. Encode and Decode Strings

2 min read

Prompt

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.

Examples

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: [""]

Solution

In C++

const char del = '?';
 
string encode(vector<string>& strs) {
	string str_acc = "";
	for (const auto& str : strs) {
		str_acc += to_string(str.size()) + del + str;
	}
	return str_acc;
}
 
  
vector<string> decode(string s) {
	vector<string> answer;
	stringstream ss(s);
	string buf;
	
	while (getline(ss, buf, del)) {
		int num = stoi(buf);
		string temp(num, '\0');
		ss.read(&temp[0], num);
		answer.push_back(temp);
	}
	return answer;
}

Explanation

Kind of how blocks in the Freelist are setup, we can represent a list of blocks of data with size metadata. We use a delimiter so we know how far to parse.

Graph View