Python程式：查詢最長平衡子序列的長度

假設我們有一個包含括號 "(" 和 ")" 的字串 s，我們需要找到最長平衡括號子序列的長度。

例如，如果輸入是 s = "())(()("，則輸出為 4，因為我們可以選擇 "()()" 作為子序列。

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

  • res := 0

  • n := s 的長度

  • close := 0

  • for i in range(n - 1, -1, -1):

    • if s[i] == ")": then

      • close := close + 1

    • else:

      • if close > 0: then

        • close := close - 1

        • res := res + 2

  • return res

讓我們來看下面的實現，以便更好地理解：

示例

 線上演示

class Solution:
   def solve(self, s):
      res = 0
      n = len(s)
      close = 0
      for i in range(n - 1, -1, -1):
         if s[i] == ")":
            close += 1
         else:
            if close > 0:
               close -= 1
                  res += 2
            return res
ob = Solution()
s = "())(()("
print(ob.solve(s))

輸入

"())(()("

輸出

4

更新於：2020年10月10日

311 次瀏覽

開啟您的職業生涯

完成課程獲得認證

開始學習
廣告