---
title: 【LeetCode】0032. Longest Valid Parentheses
date: 2018-12-21
is_modified: false
disqus: cynthiahackmd
categories:
- "面試刷題"
tags:
- "LeetCode"
---

{%hackmd @CynthiaChuang/Github-Page-Theme %}
<br>

Given a string containing just the characters `'('` and `')'`, find the length of the longest valid (well-formed) parentheses substring.
<!--more-->
<br>

**Example 1:**

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

**Example 2:**

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

<br>

**Related Topics:** `String`、`Stack`、`Dynamic Programming`

## 解題邏輯與實作
這題算是 [Valid Parentheses](/TQhIATq2RZmiPVi8w2TFSw) 的進階版，不過還是可以用 Stack 來解決。

### Stack
由於我需要知道知道它們之間的距離，所以推入 stack 時我除了記錄括號外，也記錄他們的索引值。
1. 開始前先 `push ( -1, ')' )` 進入 stack
2. 依序讀入字串
1. 若遇到左括號，`push (index , '(' )`
2. 若遇到右括號，則檢查stack最上層
1. 若為右括號，`push (index , ')' )`
2. 若為左括號，將其 pop 並檢查長度，檢查方式為：使用目前索引值減掉目前最上層的索引值後，與目前所記錄的最長合法長度取 max。

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 參考作法 → [傳送門](https://leetcode.com/articles/longest-valid-parentheses/)

## 其他連結
1. [【LeetCode】0000. 解題目錄](/x62skqpKStKMxRepJ6iqQQ)

<br><br>

> **本文作者**： 辛西亞．Cynthia
> **本文連結**： [辛西亞的技能樹](https://cynthiachuang.github.io/LeetCode-0032-Longest-Valid-Parentheses) / [hackmd 版本](https://hackmd.io/@CynthiaChuang/LeetCode-0032-Longest-Valid-Parentheses)
> **版權聲明**： 部落格中所有文章，均採用 [姓名標示-非商業性-相同方式分享 4.0 國際](https://creativecommons.org/licenses/by-nc-sa/4.0/deed.en) (CC BY-NC-SA 4.0) 許可協議。轉載請標明作者、連結與出處！