C++で括弧の各ペア間の部分文字列を反転する方法

問題概要

小文字の英字と括弧で構成された文字列 s が与えられます。最も内側の括弧から順に、対応する括弧のペアの中にある文字列を反転していき、最終的な結果には括弧が一切含まれないようにします。

たとえば、入力が "(hel(lowo)rld)" の場合、出力は "dlrlowoleh" になります。処理は次のように段階的に進みます。

"(hel(lowo)rld)" → "(hel(owol)rld)" → "dlrlowoleh"

まず最も内側の (lowo) が反転されて owol となり、続いて外側の括弧内全体 helowolrld が反転されて dlrlowoleh が得られます。

解法のアプローチ

この問題は、括弧同士の対応関係を事前に記録しておき、文字列上を「行ったり来たり」しながら読み進めることで、一度の走査で解くことができます。手順は以下の通りです。

• n を文字列のサイズとし、長さ n の配列 par を用意します。さらにスタック st を定義します。
• i を 0 から n − 1 まで走査します。
  • s[i] が開き括弧「(」であれば、そのインデックス i を st にプッシュします。
  • s[i] が閉じ括弧「)」であれば、st からポップした値を j とし、par[i] := j および par[j] := i として、両者の対応関係を記録します。
• 空の文字列 ret を定義します。
• i := 0、d := 1（d は移動方向を表す変数）とし、i < n の間、i を d ずつ増減させながらループします。
  • s[i] が開き括弧または閉じ括弧であれば、i := par[i] としてペアとなる括弧の位置へジャンプし、移動方向を反転（d := -d）します。
  • それ以外の文字であれば、ret の末尾に s[i] を追加します。
• ret を返します。

この手法のポイントは、括弧に到達するたびにペアの相手側へ移動して方向を反転させることで、実際に文字列を反転する操作を一切行わずに、あたかも内側から反転済みの状態で文字を読み取れる点です。計算量は O(n)、追加で必要なメモリも O(n) にとどまり、非常に効率的です。

C++での実装例

以下の実装を見ると、仕組みがより明確に理解できるでしょう。

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    void out(vector <int>& v){
        for(int i = 0; i < v.size(); i++){
            cout << v[i] << " ";
        }
        cout << endl;
    }
    string reverseParentheses(string s) {
        int n = s.size();
        vector <int> par(n);
        stack <int> st;
        // 開き括弧と閉じ括弧の対応関係を記録する
        for(int i = 0; i < n; i++){
            if(s[i] == '('){
                st.push(i);
            }
            else if(s[i] == ')'){
                int j = st.top();
                st.pop();
                par[i] = j;
                par[j] = i;
            }
        }
        string ret = "";
        // 括弧に到達したらペアの位置へジャンプし、進行方向を反転する
        for(int i = 0, d = 1; i < n; i += d){
            if(s[i] == '(' || s[i] == ')'){
                i = par[i];
                d = -d;
            }
            else{
                ret += s[i];
            }
        }
        out(par);
        return ret;
    }
};
main(){
    Solution ob;
    cout << (ob.reverseParentheses("(hel(lowo)rld)"));
}

入力

"(hel(lowo)rld)"

出力

13 0 0 0 9 0 0 0 0 4 0 0 0 0
dlrlowoleh

出力の最初の行は、配列 par の内容（各括弧とそのペアのインデックス）を示しています。この例では、インデックス 0 の「(」とインデックス 13 の「)」、およびインデックス 4 の「(」とインデックス 9 の「)」がそれぞれペアになっていることが確認できます。2 行目が最終的な答えです。