C++でエンコードされた文字列をデコードする方法

エンコードされた文字列を受け取り、それを復号した結果を返すプログラムを考えてみましょう。ここで使われるエンコードのルールは「k[encoded_string]」という形式です。これは、角括弧の中の文字列がちょうど k 回繰り返されることを表しています。また、元のデータには数字が一切含まれていないと仮定できるため、数字は必ず繰り返し回数 k を意味します。

たとえば、入力が "1[ba]2[na]" であれば、「ba」が1回、「na」が2回繰り返されるため、出力は "banana" になります。

解法の考え方：スタックを活用する

このような入れ子構造を持つ問題は、スタック（stack）を使うのが定番のアプローチです。文字を左から順に読み込みながらスタックに積んでいき、閉じ括弧 ']' を見つけた時点で、対応する開き括弧 '[' までさかのぼって文字列と繰り返し回数を取り出し、展開結果を再びスタックに戻します。これにより、「2[a3[c]]」のようにネストした括弧を含むケースでも正しく処理できます。

アルゴリズムの手順

1. 空のスタックを1つ用意し、インデックス i を 0 で初期化する。
2. i が文字列のサイズ未満である限り、以下を繰り返す。
   • s[i] が ']' の場合：
     • '[' が現れるまでスタックから要素を取り出し、括弧の内側にある文字列 res を組み立てる。
     • n := 0 で初期化する。
     • スタックが空でなく、かつスタックの先頭が数字の間、桁ごとの値を加算して実際の整数 n を復元する。
     • j を 1 から n までループさせ、さらに x を 0 から res のサイズまでループさせ、res[x] をスタックに挿入する。
   • それ以外の場合は、s[i] をそのままスタックに挿入する。
   • i を 1 増やす。
3. ans := 空文字列として初期化する。
4. スタックが空になるまで、「ans := スタックの先頭要素 + ans」として要素をポップしていく。
5. ans を返す。

C++による実装例

それでは、上記の手順をC++で実装してみましょう。

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    string decodeString(string s) {
        stack <char> st;
        int i = 0;
        while(i<s.size()){
            if(s[i] == ']'){
                string res = "";
                while(st.top()!='['){
                    res = st.top() + res;
                    st.pop();
                }
                st.pop();
                int n = 0;
                int x = 1;
                while(!st.empty() && st.top()>='0' && st.top()<='9'){
                    n = n + (st.top()-'0')*x;
                    x*=10;
                    st.pop();
                }
                for(int j = 1; j <= n; j++){
                    for(int x = 0; x < res.size();x++){
                        st.push(res[x]);
                    }
                }
            }
            else{
                st.push(s[i]);
            }
            i++;
        }
        string ans ="";
        while(!st.empty()){
            ans = st.top() + ans;
            st.pop();
        }
        return ans;
    }
};
main(){
    Solution ob;
    cout << ob.decodeString("1[ba]2[na]");
}

コードのポイント

• 括弧内の文字列の抽出：スタックはLIFO（後入れ先出し）なので、ポップすると文字は逆順に取り出されます。そこで res = st.top() + res とすることで、元の順序を保ったまま文字列を組み立てています。
• 繰り返し回数の復元：数字もスタックには1文字ずつ積まれているため、ポップする際は下位の桁から順に現れます。x *= 10 で桁位置をずらしながら加算することで、正しい整数値 n を復元しています。
• ネストへの対応：展開結果を再びスタックに戻す仕組みのため、「2[a3[c]]」のような多重ネストのパターンでも、外側の括弧を処理する時点で内側はすでに展開済みになっています。

実行結果

入力

"1[ba]2[na]"

出力

"banana"

まとめ

このアルゴリズムでは、各文字はスタックに対して限られた回数しか出入りせず、処理時間は主に最終的な出力文字列の長さに依存します。括弧や繰り返しを含む文字列の解析では、スタックを使ったアプローチが非常に有効です。このパターンは構文解析やJSON風データの処理などにも応用できるので、ぜひ覚えておきましょう。