【LeetCode】0032. Longest Valid Parentheses

| | |

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

Example 1:

1
2
3
Input: "(()"
Output: 2
Explanation: The longest valid parentheses substring is `"()"`

Example 2:

1
2
3
Input: "`)()())`"
Output: 4
Explanation: The longest valid parentheses substring is `"()()"`


Related Topics:String、Stack、Dynamic Programming

解題邏輯與實作

這題算是 Valid Parentheses 的進階版，不過還是可以用 Stack 來解決。

Stack

由於我需要知道知道它們之間的距離，所以推入 stack 時我除了記錄括號外，也記錄他們的索引值。

  1. 開始前先 push ( -1, ')' ) 進入 stack
  2. 依序讀入字串
    1. 若遇到左括號，push (index , '(' )
    2. 若遇到右括號，則檢查stack最上層
      1. 若為右括號，push (index , ')' )
      2. 若為左括號，將其 pop 並檢查長度，檢查方式為：使用目前索引值減掉目前最上層的索引值後，與目前所記錄的最長合法長度取 max。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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 解了？

DP 參考作法 → 傳送門

其他連結

  1. 【LeetCode】0000. 解題目錄