Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.

Example 1:

 123 Input: "(()" Output: 2 Explanation: The longest valid parentheses substring is "()" 

Example 2:

 123 Input: ")()())" Output: 4 Explanation: The longest valid parentheses substring is "()()" 

Related Topics:StringStackDynamic Programming

## 解題邏輯與實作

### Stack

1. 開始前先 push ( -1, ')' ) 進入 stack
2. 依序讀入字串
1. 若遇到左括號，push (index , '(' )
2. 若遇到右括號，則檢查stack最上層
1. 若為右括號，push (index , ')' )
2. 若為左括號，將其 pop 並檢查長度，檢查方式為：使用目前索引值減掉目前最上層的索引值後，與目前所記錄的最長合法長度取 max。
 1234567891011121314151617 from pythonds.basic.stack import Stack class Solution: def longestValidParentheses(self, s): max_valid = 0 stack = Stack() stack.push((-1,')')) for i, char in enumerate(s) : if char == '(': stack.push((i,char)) else: if stack.peek()[1] == ")" : stack.push((i,char)) else: stack.pop() max_valid = max(max_valid, i - stack.peek()[0]) return max_valid 

### Dynamic Programming

Po 文前打 Tag 時才發現，這題的標籤是 DP 反而沒有 Stack 耶～！

DP 參考作法 → 傳送門