資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究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 次瀏覽
廣告