Namaran

Code daily. Without assist.

2026-11-13

decode.cpp

std::string decode(const std::map<std::string, char>& codes, const std::string& bits) {
}

codes は、'0' と '1' からなる符号から1文字への表です。符号の長さはそろっていませんが、どの符号も、ほかの符号の先頭部分にはなっていません。符号を並べてつないだビット列 bits を受け取り、元の文字列を返す decode を書いてください。bits は必ず符号の並びに切り分けられ、空なら空文字列を返します。

入力例 1

decode({{"0", 'a'}, {"10", 'b'}, {"11", 'c'}}, "010110")

出力例 1

"abca"

入力例 2

decode({{"0", 'a'}, {"10", 'b'}, {"11", 'c'}}, "")

出力例 2

""

入力例 3

decode({{"00", 'x'}, {"01", 'y'}, {"1", 'z'}}, "1001101")

出力例 3

"zxzzy"
Reference

Reference

std::string decode(const std::map<std::string, char>& codes, const std::string& bits) {
    std::string out;
    std::string buf;
    for (char b : bits) {
        buf += b;
        if (auto it = codes.find(buf); it != codes.end()) {
            out += it->second;
            buf.clear();
        }
    }
    return out;
}

符号の長さがそろっていないので、bits を決まった幅で切ることはできません。代わりに先頭から1ビットずつ buf に足し、buf が表のどれかの符号と一致した時点で、その文字を確定して buf を空に戻します。これは参考実装で、唯一の正解ではありません。

一致した時点で確定してよいのは、どの符号もほかの符号の先頭部分になっていないからです。buf が符号 "10" と一致したなら、"10" で始まる長い符号は表に無いので、もっと読み進めて別の符号になる可能性はありません。入力例3では、1 が z、続く 0 はどれとも一致せず、00 で x になり、残りの 1 1 01 が z z y になります。表は const 参照で受けているので、引くには operator[] ではなく find を使います。operator[] は無いキーを挿入する関数で、const の std::map には呼べません。bits が空ならループが回らず、空の out を返します。