C++で文字列リストをエンコード・デコードするアルゴリズムの実装方法

文字列のリストが与えられたとき、そのリスト全体を1つの文字列にエンコードするアルゴリズムを設計し、さらにエンコードされた文字列を元のリストへ復元（デコード）する仕組みを実装することを考えます。エンコーダーとデコーダーはそれぞれ別のマシンに配置されており、以下のような2つの関数として構成されます。

マシン1（送信側）が持つ関数

string encode(vector<string> strs) {
    // 文字列を読み込み、encoded_string を返す
}

マシン2（受信側）が持つ関数

vector<string> decode(string s) {
    // encoded_string をデコードし、strs を返す
}

例えば、入力が {"hello", "world", "coding", "challenge"} の場合、出力は次のようになります。

• エンコード後の文字列： 5#hello5#world6#coding9#challenge
• デコード後のリスト： [hello, world, coding, challenge]

解決のアプローチ

この問題は、各文字列を「長さ + 区切り文字(#) + 文字列本体」という形式で連結することで解決できます。この方式を採用すれば、文字列本体に「#」や数字が含まれていても、先頭の長さ情報に基づいて正確に境界を判定できるため、安全にエンコード・デコードが行えます。

具体的な手順は以下の通りです。

• encode() 関数を定義し、文字列配列 strs を受け取ります。
• ret := 空文字列 で初期化します。
• i := 0 から strs のサイズ未満まで、i を1ずつ増やしながら繰り返します。
  • ret := ret + 「strs[i] のサイズ」+ "#" + strs[i]
• ret を返します。
• getNext() 関数を定義し、x（検索対象の文字）、start（検索開始位置）、s（対象文字列）を受け取ります。
• idx := s のサイズ（見つからなかった場合の初期値）とします。
• i := start から s のサイズ未満まで繰り返します。
  • s[i] が x と一致したら、idx := i としてループを抜けます。
• idx を返します。
• decode() メソッドを定義し、文字列 s を受け取ります。
• 結果格納用の配列 ret を定義します。
• i := 0、n := s のサイズ とします。
• i < n の間、以下を繰り返します。
  • hashPos := getNext('#', i, s) — 次の「#」の位置を取得します。
  • len := s の i 番目から hashPos - i 文字分の部分文字列を整数に変換します（＝文字列の長さ）。
  • i := hashPos + 1 と更新します。
  • s の i 番目から len 文字分の部分文字列を ret の末尾に追加します。
  • i := i + len と更新します。
• ret を返します。

実装例

理解を深めるために、以下のC++による実装を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
    cout << "[";
    for(int i = 0; i<v.size(); i++){
        cout << v[i] << ", ";
    }
    cout << "]"<<endl;
}
class Codec {
public:
    string encode(vector<string>& strs) {
        string ret = "";
        for (int i = 0; i < strs.size(); i++) {
            ret += to_string(strs[i].size()) + "#" + strs[i];
        }
        return ret;
    }
    int getNext(char x, int start, string s){
        int idx = s.size();
        for (int i = start; i < s.size(); i++) {
            if (s[i] == x) {
                idx = i;
                break;
            }
        }
        return idx;
    }
    vector<string> decode(string s) {
        vector<string> ret;
        int i = 0;
        int 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;
    }
};
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));
}

入力

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

出力

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

このように「長さ#文字列」の形式で連結していくことで、空白文字や記号を含む文字列でも確実に元の状態へ復元できます。エンコード・デコードともに処理時間は全文字数に対して線形（O(n)）となるため、効率的な手法と言えます。