C++で有効な括弧列を作るための最小削除アルゴリズム

文字列 s が、'('・')' および小文字の英字で構成されているとします。このとき、残った括弧列が「有効」になるように、括弧 '(' または ')' を任意の位置から最小限削除し、有効な文字列を1つ返すことを考えます。

括弧列が有効であるとは、次の条件を満たすことです。

• 空文字列である、または小文字のみを含む

• AB(A と B を連結した形)と表せる。ただし A・B はそれぞれ有効な文字列

• (A) と表せる。ただし A は有効な文字列

たとえば、入力が "a)b(c)d" の場合、出力は "ab(c)d" となります。

アルゴリズムの考え方

この問題はスタックを使うことで効率的に解けます。対応する開き括弧を持たない閉じ括弧、および閉じ括弧を持たない余分な開き括弧を検出してマークし、最後にそれらを取り除くという流れです。

解法の手順

• 整数型のスタック st を定義する
• i を 0 から s のサイズまでループする
  • s[i] が '(' の場合:i を st にプッシュする
  • s[i] が ')' の場合:
    • スタックが空でなければポップする(対応する開き括弧が見つかった)
    • 空の場合は s[i] = '*' とマークする(削除対象)
• st が空でない間、次を繰り返す(余った開き括弧の処理)
  • s[スタックの先頭要素] = '*' とマークする
  • スタックからポップする
• ans を空文字列として初期化する
• i を 0 から s のサイズ − 1 までループし、s[i] が '*' でなければ ans に追加する
• ans を返す

以下の実装例を見ると、理解がより深まるでしょう。

実装例

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   string minRemoveToMakeValid(string s) {
      stack <int> st;
      for(int i = 0; i < s.size(); i++){
         if(s[i] == '(')st.push(i);
         else if(s[i] == ')'){
            if(!st.empty())st.pop();
            else s[i] = '*';
         }
      }
      while(!st.empty()){
         s[st.top()] = '*';
         st.pop();
      }
      string ans = "";
   for(int i = 0; i < s.size(); i++){
      if(s[i] != '*')ans += s[i];
    }
    return ans;
   }
};
main(){
   Solution ob;
   cout << (ob.minRemoveToMakeValid("a)b(c)d"));
}

入力

"a)b(c)d"

出力

ab(c)d

計算量

時間計算量は O(n)、空間計算量は O(n) です(n は文字列の長さ)。各文字を高々1回ずつ処理し、スタックには最大で n 個のインデックスが格納されるためです。