19 Sep 2023, 3:21 PM
19 Sep 2023, 3:21 PM

6. Encode and Decode Strings

#lintcode/659

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.

Please implement encode and decode.

Example:

Encode:
Input: ["lint","code","love","you"]
Output: "lint:;code:;love:;you"

Decode:
Input: "lint:;code:;love:;you"
Output: ["lint","code","love","you"]

Solution

Solution in C++ encoding the size of each string

Since using any character as separator isn't a good idea (if it appeared inside a string, it would be a problem), we simply encode the size of each string behind.
In addition, we use a special character to distinguish the size of each string from the actual string.

Example:

Encode:
Input: ["lint","9ode","lovelovelove","###"]
Output: "4#lint4#9ode12#lovelovelove3####"

The decode method is intuitable, we iterate over the string and as soon as we find a number, it's the size of the next string.

Example:

Decode:
Input: "4#lint4#9ode12#lovelovelove3####"
Output: ["lint","9ode","lovelovelove","###"]

Here's the implementation of encode and decode:

string encode(vector<string> &strs) {
	char separator = '#';
	string ans = "";
	
	for(string str : strs)
		ans += to_string(str.size()) + separator + str;
	
	return ans;
}

vector<string> decode(string &str) {
	char separator = '#'; 
	vector<string> ans;
	string strLength = "";
	int i = 0;

	while(i < str.size()) {
		/*
			if the current character isn't the separator,
			it must be the size of the next string 
		*/ 
		if(str[i] != separator) {
			strLength += str[i];
			i++;
		}
		/*
			if the current character is the separator,
			str.substr(i + 1, sizeOfString) it's a word
		*/ 
		else {
			int length = stoi(strLength);
			string currStr = str.substr(i + 1, length);
			ans.push_back(currStr);
			//move on the next word
			i += length + 1;
			strLength = "";
		}
	}
	return ans;
}