Pythonで括弧列を有効にするための最小追加数を求める方法

問題の概要

'(' と ')' だけで構成された文字列 S が与えられます。任意の位置に最小限の括弧を追加して、結果として得られる文字列を「有効な括弧列」にすることを考えます。括弧列が有効であるとは、次のいずれかの条件を満たすことを指します。

• 空文字列である
• XY(X と Y を連結した形)と表せ、X と Y がどちらも有効な文字列である
• (A) という形で表せ、A が有効な文字列である

たとえば、文字列が "()))((" の場合、これを有効にするには 4 つの括弧を追加する必要があります。

解法のアプローチ

この問題はスタックの考え方を使うとシンプルに解決できます。具体的な手順は以下の通りです。

1. S が空文字列の場合は 0 を返します。
2. 対応の取れていない括弧を保持するためのリスト temp を用意します。
3. 文字列 S の各文字 i に対して以下の処理を行います。
   • i が開き括弧 '(' の場合は、temp に追加(プッシュ)します。
   • i が閉じ括弧 ')' の場合は、temp が空でなく、末尾の要素が '(' であればペアとして取り除きます。そうでなければ i を temp に追加します。
4. すべての処理が終わった後、temp のサイズを返します。この値が追加すべき括弧の最小数になります。

処理完了時に temp に残るのは、ペアを作れずに余った括弧だけです。開き括弧が余っていれば対応する閉じ括弧を、閉じ括弧が余っていれば対応する開き括弧を追加すればよいため、残りの要素数がそのまま答えになります。

実装例

class Solution:
   def minAddToMakeValid(self, S):
      if not S:
         return 0
      temp = []
      for i in S:
         if i == '(': 
            temp.append(i)
         else:
            if len(temp) > 0 and temp[-1] == '(': 
               temp.pop()
            else:
               temp.append(i)
      return len(temp)

ob = Solution()
print(ob.minAddToMakeValid("()))(("))

入力

"()))(("

出力

4

計算量について

各文字を一度だけ走査し、スタックへの追加・削除はすべて定数時間で行えるため、時間計算量は O(n) です。空間計算量は、すべての文字が開き括弧であるような最悪ケースで O(n) となります。

O(1) メモリで解く別解

スタックの代わりにカウンターを2つ使えば、追加のメモリなしで同じ結果が得られます。「まだ対応する閉じ括弧を待っている開き括弧の数」と「すでに対応不可能と確定した余分な閉じ括弧の数」を数え、最後にその合計を返すだけです。

def minAddToMakeValid(self, S):
   open_count = 0
   close_count = 0
   for c in S:
      if c == '(': 
         open_count += 1
      else:
         if open_count > 0:
            open_count -= 1
         else:
            close_count += 1
   return open_count + close_count

どちらの方法でも結果は同じですが、メモリ使用量を抑えたい場合は後者のカウンター方式が有効です。