Question statement
Design an algorithm to encode a list of strings to a single string.
The encoded string is then decoded back to the original list of strings.
Input: ["leet","code","loveeeeeeeeeee","you"]
Output: ["leet","code","loveeeeeeeeeee","you"]
Two methods are provided with following signatures to implement
The encoded string is then decoded back to the original list of strings.
Input: ["leet","code","loveeeeeeeeeee","you"]
Output: ["leet","code","loveeeeeeeeeee","you"]
Two methods are provided with following signatures to implement
string encode(vector<string> strs) // To encode vector of strings into a single string vector<string> decode(string str) // To decode string generated by encode function to its original form and return as a vector
Solution
You can use a delimiter to split values while encoding so that way when we decode we would know which delimiter to use to split and get the original word.
Here in this solution, I used N# as delimiter where N is the number of words in a letter and # is used as a delimiter.
So encoded string would look something like this after encode() method
"4#leet4#code14#loveeeeeeeeeee3#you"
Here in this solution, I used N# as delimiter where N is the number of words in a letter and # is used as a delimiter.
So encoded string would look something like this after encode() method
"4#leet4#code14#loveeeeeeeeeee3#you"
n# would tell us that we need next n characters for 1 string
4# -> next 4 words after #
4# -> next 4 words after #
14# -> -> next 14 words after #
3# -> -> next 3 words after #
So during the decoding process, check for the number and # sign to split then add N number of characters into a string to get the original word and put in a vector to return original strings.
Interesting challenges emerge when trying to encode a string
1. Convert a number to string
When we try to encode the string, we need to prefix a string with N#, where N is the size of a string.
For example, a list contains a string "code", then we need to get the size of "code" which is 4 and then prefix the string "code" with "4#code" to encode.
string s = "code"; //Non encoded string int size = s.size(); // 4 - given size of a string string number =""; number += size + '0'; // 4 + 48 = 52 , and 52 is ASCII value of 4 when adding to a char '0' cout << number << endl; // output 4
ASCII value of 0 - 9 = 48 - 57.
The logic to add a size to ascii value of '0' works great; however it will not work when we are given a size that is greater than 9.
What if string is "loveeeeeeeeeee", then size() function would return us 14, and if we try to add like this,
string s = "loveeeeeeeeeee"; //Non encoded string int size = s.size(); // 4 - given size of a string string number =""; number += size + '0'; // 14+48 would return 62, which would result into > ASCII character cout << number << endl; // output >
As you can see, that logic fails to convert 14 to a correct string thus require us to individually split the size and convert to string.
To convert any number to string, you have to split each integer, and to do that, we must use % and / get those values.
Here's a full implementation of how to convert an int number to string. For this problem, we don't have to worry about negative numbers.
//Converts a given number to string i.e 123 to "321" string numToString(int num){ string str = ""; if(num > 9){ while(num > 0){ int r = num % 10; // 3 | 2 | 1 str += r + '0'; // adding 3 | adding 2 | adding 1 to string num = num / 10; //12 | 1 | 0 } }else{ str += num + '0'; } return str; }
Now this does convert an integer to string correctly; however, this returns a string in reverse order since we are appending remainder of a number to string. We must convert this string in reverse to obtain the correct number.
Reverse a string
Here's how you can reverse any string. Basically have to map first to last and swap them as you iterate through half the size of a string. You can check comments on code to understand the example.
Here's implementation of how to reverse a string:
/* Follows this step for "1234" string step 1: 1 swap with 4 result : 4231 step 2: 2 swap 3 result : 4321 string size/2 - iterations. Another example: "123" - size/2 = 1 iteration step 1 - swap 1 and 3 result = "321" Done! */ //reverses string, example - 231 to 132. string reverseString(string str){ //string reversed = ""; for(int i= 0; i< str.size()/2; i++){ int index = (str.size()-1) - i ; // 2 -0, 2, 2-1 - 1 //swap char c = str[i]; str[i] = str[index]; str[index] = c; } return str; }
The above method will ensure that when we are prefixing string with N#, we are prefixing with correct string value of size.
Decode a string
We would face a similar problem of converting a string into an integer number in order to know the iteration number to get the correct string.
For example, in string "14#loveeeeeeeeeee", we will have to extract values till #, which will be "14" in string format.
To loop through 14 characters, we need an integer value of "14" thus, we will need to covert string into an integer.
Here's how you can convert a string to number, given that string does contain correct integer value.
/*Example: string str = "14"; str[1] = 1; str[2] = 4; n=0 n = n*10+ (str[1] -'0') = 0+ (49-48)= 0+1 = 1 n = 1*10+ (str[2] -'0') = 10+(52-48)=10+4= 14 Done! 14 is the number. You have to multiply n with 10 to get later values. */ //Converts a given string to a number i.e "99" to 99. int strToNum(string str){ int num = 0; if(str.size() > 1){ for(auto i: str){ num = num*10 + (i - '0'); } return num; }else{ int value = (int) str[0]; value -= '0'; // minus to get to value 9... 9=57, 0=48 --> 57-48 = 9 return value; } }
All these helper methods are needed in order to properly encode and decode a string.
Implementation of solution
//Encode string with N#String i.e 4#Ajay <- 4 (num of characters) # (delimiter) and Ajay is string. string encode(vector<string>& strs) { string str = ""; for(auto i: strs){ //str += i.size() + '0'; // This alone only works if one digit number, doesn't work for 2digits num. str += reverseString(numToString(i.size())); str += '#'; str += i; } return str; } //Decoding a given encoded string. vector<string> decode(string s){ vector<string> strs; string num; string str=""; int currentNum = 0; for(int i=0;i<s.size();i++){ if(s[i] == '#'){ currentNum = strToNum(num); num = ""; for(int j = i+1; j <= i+currentNum; j++){ str += s[j]; } strs.push_back(str); str = ""; i += currentNum; //resetting i to resume loop. }else{ num += s[i]; } } return strs; } int main() { //vector<string> strs = {"AjayVeryLongStringWithoutAnySpacesOrSpecialCharactersRepeatedManyTimesVeryLongStringWithoutAnySpacesOrSpecialCharactersRepeatedManyTimes 12#space->VeryLongStringWithoutAnySpacesOrSpecialCharactersRepeatedManyTimesVeryLongStringWithoutAnySpacesOrSpecialCharactersRepeatedManyTimesAjay"}; vector<string> strs = {"leet", "code", "loveeeeeeeeeee", "you"}; string str = encode(strs); cout << "Encoded String-> " << str << endl; vector<string> de; de = decode(str); cout << "decoded string-> "; for(auto i: de){ cout << i << " "; } //cout << reverseString("231") << endl; return 0; }
Full source code is available here : https://github.com/apprajapati9/CPlusPlus/blob/master/C%2B%2B/Leetcode/encode-decode-strings/encode-decode-%23.cpp
Another way to convert number to string
I already posted code on how to convert a number to string, but it required us to have an additional step of reversing string after the conversion.
For example, "1234" would be converted to "4321" and after that we have to reverse the string which would result into "1234" which is a correct number in string format to encode strings.
Here's another way of converting an integer to number which doesn't require us to reverse a string after. Here instead of dividing by 10, we are dividing it by the highest divisor of the number possible to get the first digit from right side and then reducing that divisor by 10.
For example,
number 1234
1234 % 10 -> Would give us 4
1234 % 1000 -> would give us 1
So we are going to divide the value using 1000,100,10 in order to get the number from right to left, instead of previous method where we divided by 10 and got the right most integer value. Check the picture to understand.
string numToString(int num){ string str = ""; int save = num; int divisor = 1; while(num > 10){ num = num / 10; divisor *= 10; } while(divisor != 1){ int right = save / divisor;// 1234/ 1000 - 1, 2, 3 save %= divisor;// 234 , 34, 4 divisor /= 10; str += right + '0'; } str += save + '0'; return str; }
The above code is following these steps which mitigate the necessity to reverse a string.
Source code here : https://github.com/apprajapati9/CPlusPlus/blob/master/C%2B%2B/Leetcode/encode-decode-strings/convert-num-to-string.cpp
Hopefully this explanation would solidify your understanding of this problem.
For any questions or suggestions, please comment and thank you.
Happy coding!
0 Comments