Encode and Decode Strings - Mã hóa và giải mã danh sách chuỗi

Thiết kế thuật toán mã hóa danh sách chuỗi thành một chuỗi, và giải mã ngược lại. Định dạng: độ_dài#chuỗi cho mỗi phần tử.

Ví dụ: {"hello","world","coding","challenge"} → "5#hello5#world6#coding9#challenge".

Giải thuật

Encode: nối to_string(len) + "#" + str cho mỗi chuỗi.
Decode: đọc số trước # làm độ dài, cắt chuỗi con tương ứng, lặp lại.

Cài đặt C++

#include <bits/stdc++.h>
using namespace std;

void print_vector(vector<string> v) {
    cout << "[";
    for (auto& s : v) cout << s << ", ";
    cout << "]" << endl;
}

class Codec {
public:
    string encode(vector<string>& strs) {
        string ret;
        for (auto& s : strs)
            ret += to_string(s.size()) + "#" + s;
        return ret;
    }

    int getNext(char x, int start, string s) {
        for (int i = start; i < s.size(); i++)
            if (s[i] == x) return i;
        return s.size();
    }

    vector<string> decode(string s) {
        vector<string> ret;
        int i = 0, n = s.size();
        while (i < n) {
            int hashPos = getNext('#', i, s);
            int len = stoi(s.substr(i, hashPos - i));
            i = hashPos + 1;
            ret.push_back(s.substr(i, len));
            i += len;
        }
        return ret;
    }
};

int main() {
    Codec ob;
    vector<string> v = {"hello", "world", "coding", "challenge"};
    string enc = ob.encode(v);
    cout << "Encoded String " << enc << endl;
    print_vector(ob.decode(enc));
    return 0;
}

Đầu vào

{"hello", "world", "coding", "challenge"}

Đầu ra

Encoded String 5#hello5#world6#coding9#challenge [hello, world, coding, challenge, ]