Solution: Encode and Decode Strings

Let's solve the Encode and Decode Strings problem using the Bitwise Manipulation pattern.

Statement

Create a method, encode, that converts an array of strings into a single string and then sends it over the network. Create another method, decode, that takes the encoded string and converts it back into the original array of strings.

Constraints:

  • 11 \leq strings.length 100\leq 100
  • 00 \leq strings[i].length 100\leq 100
  • strings[i] consists of any possible combinations of characters from 256 valid ASCII characters.

Solution

Although there can be several mechanisms to encode and decode strings, the presented approach is based on the encoding used in HTTP v1.1.

For encoding, we will initialize an empty string that will store our encoded string. After that, we will iterate over the input string array and calculate each string’s length in 4 bytes. For this process, the length will be computed, followed by the loop of range 4. In each iteration, the right shift operator shifts the bits of the number by (i * 8) positions, followed by appending it to the bytes array. Finally, the array of bytes is reversed, and the 4-byte string length is appended with the string and added to the encoded string variable. These steps are repeated for each string in the array.

For decoding, we will initialize a pointer, i, which will iterate over the encoded string. As we already know, the first four characters will represent the length of the first string. We will convert that 4-byte string to an integer. The integer will be used to extract the desired string, add it to the decoded array, and move the pointer for extracting the next strings.

Let’s look at the following illustration to get a better understanding of the solution:

Level up your interview prep. Join Educative to access 80+ hands-on prep courses.