Pythonで有効な括弧を作成するために必要な最小限の削除を見つけるプログラム

括弧'（'、'）'と小文字の英語文字を含む文字列sがあるとします。結果の括弧文字列が有効になり、最終的に有効な文字列を返すように、最小数の括弧（'（'または'）'、任意の位置から）を削除する必要があります。ここで、括弧文字列は、これらの基準がすべて満たされている場合に有効です-

• 文字列は空で、小文字のみが含まれている、または

• 文字列は、AB（AとBを連結したもの）として記述できます。ここで、AとBは有効な文字列、または

• 文字列は（A）の形式で記述できます。ここで、Aは有効な文字列です。

したがって、入力がs ="m）n（o）p"の場合、出力は "mn（o）p"

これを解決するには、次の手順に従います-

• スタック：=新しいリスト

• インデックス：=新しいセット

• i：=0

• sの各cについて、実行します

  • cが'（'と同じ場合、

    • iをスタックにプッシュ

  • それ以外の場合、cが'）'と同じ場合、

    • スタックのサイズが0と同じ場合、

      • インデックスにiを挿入

    • それ以外の場合

      • スタックからポップ

    • i：=i + 1

• ret：=空白の文字列

• インデックス：=すべての要素をインデックスに格納する

• 0からs-1のサイズのiの場合、実行します

  • インデックスに登録されていない場合は、

    • ret：=ret + s [i]

• retを返す

例

理解を深めるために、次の実装を見てみましょう-

def solve(s):
   stack = []
   indexes = set()
   i = 0

   for c in s:
      if c == '(':
         stack.append(i)
      elif c == ')':
         if len(stack) == 0:
            indexes.add(i)
         else:
            stack.pop()
      i += 1

   ret = ''
   indexes = indexes.union(stack)
   for i in range(len(s)):
      if i not in indexes:
         ret += s[i]

   return ret

s = "m)n(o)p"
print(solve(s))

入力

"m)n(o)p"

出力

mn(o)p