Python中使括號有效所需的最小新增

假設我們有一個包含 '(' 和 ')' 括號的字串 S，我們需要在任意位置新增最少的括號，以便生成的括號字串有效。當且僅當滿足以下條件時，括號字串才有效：

  • 它是空字串
  • 它可以寫成 XY（X 與 Y 連線），其中 X 和 Y 是有效的字串
  • 它可以寫成 (A)，其中 A 是一個有效的字串。

因此，如果字串類似於 "()))((", 則我們需要新增 4 個括號才能使字串有效。

為了解決這個問題，我們將遵循以下步驟：

  • 如果 S 為空，則返回 0
  • 計數器 count := 0，temp 為一個數組，臨時計數器 temp_counter := 0
  • 對於 S 中的每個 i
    • 如果 i 是左括號，則將 i 插入 temp
    • 否則
      • 當 temp 的長度 > 0 且最後一個元素是左括號時，刪除 temp 的最後一個元素，否則將 i 插入 temp
  • 返回 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

更新於：2020年4月30日

瀏覽量 338

開啟你的職業生涯

完成課程獲得認證

開始學習
廣告