สมมติว่าเรามีสตริง s ประกอบด้วยวงเล็บเปิดและวงเล็บปิดเท่านั้น เราต้องหาความยาวของสตริงย่อยในวงเล็บที่ถูกต้อง (ที่มีรูปแบบถูกต้อง) ที่ยาวที่สุด ดังนั้นหากอินพุตเป็นแบบ “))(())())” ผลลัพธ์จะเป็น 6 เนื่องจากสตริงที่ถูกต้องคือ “(())()”
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
สร้าง stack และใส่ -1., set ans :=0
-
สำหรับฉันอยู่ในช่วง 0 ถึงความยาวของสแต็ก – 1
-
ถ้า s[i] เปิดวงเล็บ ให้ใส่ i ลงใน stack
-
อย่างอื่น
-
ถ้า stack ไม่ว่าง และ top ของ stack ไม่ใช่ -1 และ s[stack top] กำลังเปิดวงเล็บ ดังนั้น
-
องค์ประกอบด้านบนจากสแต็ก
-
ans :=max of ans และ i – stack top
-
-
มิฉะนั้นให้แทรก i ลงใน stack
-
-
-
กลับมาอีกครั้ง
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
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
