Pythonで括弧を有効にするための最小追加

'（'および'）'括弧の文字列Sがあるとすると、任意の位置に最小数の括弧を追加して、結果の括弧文字列が有効になるようにします。括弧文字列は、-

• 空の文字列です
• XY（XとYを連結）と書くことができます。ここで、XとYは有効な文字列です
• （A）と書くことができます。ここで、Aは有効な文字列です。

したがって、文字列が "（）））（（"のような場合、文字列を有効にするには、さらに4つの括弧を追加する必要があります。

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

• Sが空の場合は、0を返します
• count：=0、tempは配列、temp_counter：=0
• for i in S
  • 括弧を開いている場合は、iをtempに挿入します
  • それ以外の場合
    • tempの長さが0より大きい場合、の最後の要素が開き括弧である場合は、tempの最後の要素を削除します。それ以外の場合は、iをtempに挿入します
• 温度のサイズを返します。

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

例

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

入力

"()))(("

出力

4