home

หน้าแรก
 Computer >> บทช่วยสอนคอมพิวเตอร์ >  >> การเขียนโปรแกรม >> Python

Longest Valid Parentheses ใน Python

กำหนดสตริงประกอบด้วย '(' และ ')' ต้องหาความยาวของ substring ที่เป็น valid parentheses ยาวที่สุด

ตัวอย่าง: "))(())())" → 6 (substring "(())()")

ขั้นตอนการแก้ปัญหา (Stack)

  • stack เริ่มต้น [-1], ans = 0
  • วน i: ถ้า s[i]=='(' → push i
  • ถ้า s[i]==')': ถ้า stack[-1]!=-1 และ s[stack[-1]]=='(' → pop, ans = max(ans, i - stack[-1])
  • มิฉะนั้น push i

ตัวอย่างโค้ด

class Solution(object):
    def longestValidParentheses(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.longestValidParentheses("))(())())"))

อินพุต

"))(())())"

เอาต์พุต

6