Python程式：查詢給定字串中最長有效括號的長度

假設我們有一個字串 s。這個 s 只包含左括號和右括號。我們需要找到最長有效（格式正確）括號子字串的長度。例如，如果輸入是“))(())())”，則結果將是 6，因為有效的字串是“(())()”。

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

  • 建立一個棧，並插入 -1。設定 ans := 0

  • 從 i=0 到字串長度-1迴圈

    • 如果 s[i] 是左括號，則將 i 插入棧中

    • 否則

      • 如果棧不為空，且棧頂不為 -1，且 s[棧頂] 是左括號，則

        • 從棧中彈出棧頂元素

        • ans := ans 和 i - 棧頂元素中的最大值

      • 否則將 i 插入棧中

  • 返回 ans

示例

讓我們看看以下實現來更好地理解：

即時演示

class Solution(object):
   def solve(self, s):
      stack = [-1]
      ans = 0
      for i in range(len(s)):
         if s[i] == "(":
            stack.append(i)
         else:
            if stack and stack[-1]!=-1 and s[stack[-1]] == "(":
               stack.pop()
               ans = max(ans,i - stack[-1])
            else:
               stack.append(i)
      return ans
ob = Solution()
print(ob.solve("))(())())"))

輸入

"))(())())"

輸出

6

更新於: 2020-12-22

95 次瀏覽

開啟你的職業生涯

透過完成課程獲得認證

開始學習
廣告