Encode and Decode Strings - CPP Solution

1. Introduction

In this blog post, we discuss an interesting problem in C++ involving encoding and decoding a list of strings. This problem is a great example of how to handle string serialization and deserialization, and it's particularly useful in understanding how to process and store strings efficiently.

Problem

The objective is to design an algorithm to encode a list of strings into a single string, and then decode it back to the original list of strings.

2. Solution Steps

1. Encoding:

- Iterate over each string in the list.

- For each string, prepend its length followed by a special character (e.g., '#') and then concatenate the string.

2. Decoding:

- Parse the encoded string to retrieve the individual strings.

- Read the length of each string, followed by the special character, and then extract the string of that length.

- Continue until the entire encoded string is processed.

3. Code Program

#include <iostream>
#include <vector>
#include <sstream>
using namespace std;

// Function to encode a list of strings
string encode(vector<string>& strs) {
    ostringstream out;
    for (string &s : strs) {
        out << s.length() << '#' << s;
    }
    return out.str();
}

// Function to decode the encoded string
vector<string> decode(string s) {
    vector<string> strs;
    int i = 0;
    while (i < s.length()) {
        int j = s.find('#', i);
        int length = stoi(s.substr(i, j - i));
        strs.push_back(s.substr(j + 1, length));
        i = j + length + 1;
    }
    return strs;
}

int main() {
    vector<string> strs = {"Hello", "World"};
    string encoded = encode(strs);
    vector<string> decoded = decode(encoded);

    cout << "Encoded: " << encoded << endl;
    cout << "Decoded:" << endl;
    for (string &s : decoded) {
        cout << s << endl;
    }
    return 0;
}

Output:

Encoded: 5#Hello5#World
Decoded:
Hello
World

Explanation:

1. The input list ["Hello", "World"] is encoded into the string "5#Hello5#World". Each string is prefixed with its length and '#'.

2. The encoded string is then decoded back into the original strings.

3. During decoding, the length of each string is determined from the characters before '#', and then the string of that length is extracted.

4. The process demonstrates an effective way to serialize and deserialize a list of strings, ensuring that each string, regardless of its content, is accurately encoded and decoded.