Python程式：計算使字串正確的最小無效括號移除數量

假設我們有一個括號字串；我們需要編寫一個函式來計算需要移除的最小括號數量，以使字串正確（每個左括號最終都會被右括號閉合）。

因此，如果輸入類似於 "(()))("，則輸出將為 2，因為正確的字串是 "(())"，移除 ")("。

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

  • total := 0, temp := 0
  • 對於s中的每個字元p，執行以下操作
    • 如果p與"("相同，則
      • total := total + 1
    • 否則，當p與")"相同且total不為0時，則
      • total := total - 1
    • 否則，
      • temp := temp + 1
  • 返回 total + temp

讓我們看看以下實現，以便更好地理解 -

示例

 線上演示

class Solution:
   def solve(self, s):
      total = 0
      temp = 0
      for p in s:
         if p == "(":
            total += 1
         elif p == ")" and total:
            total -= 1
         else:
            temp += 1
      return total + temp
ob1 = Solution()
string = "(()))("
print(ob1.solve(string))

輸入

"(()))("

輸出

2

更新於: 2020年10月20日

383 次瀏覽

開啟你的 職業生涯

透過完成課程獲得認證

開始學習
廣告