###### tags: `Leetcode` `hard` `dynamic programming` `stack` `python` `Top 100 Liked Questions`

# 32. Longest Valid Parentheses

## [題目來源:] https://leetcode.com/problems/longest-valid-parentheses/

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


#### [圖片來源:] https://leetcode.com/problems/longest-valid-parentheses/

## 解題想法:
1. stack:較為直觀 紀錄左括號的位置 每次遇到右括號，先pop
2. DP: dp[i]: s[i:]包含s[i]的最長有效匹配括號子串長度 (較難解釋，可以直接看代碼操作一次)

## Python (法1: stack):

class Solution(object):
    def longestValidParentheses(self, s):
        """
        :type s: str
        :rtype: int
        """
        res=0
        stack=[-1] #需要有個起始位置守門員
        for pos,char in enumerate(s):
            if char=='(': #左括號 正常加入其位置
                stack.append(pos) 
            else: #遇到右括 先pop
                stack.pop()
                if not stack: #若刪完為空 表示沒起始位置
                    stack.append(pos) #把當前右括的位置作為新守門員
                else:
                    res=max(res,pos-stack[-1])
        return res

result=Solution()
ans=result.longestValidParentheses(s="(()(()))")
print(ans)

## Python (法2: dp):

class Solution(object):
    def longestValidParentheses(self, s):
        """
        :type s: str
        :rtype: int
        """
        #dp[i]: s[i:]包含s[i]的最長有效匹配括號子串長度
        res=0
        dp=[ 0 for _ in range(len(s))]
        i=len(s)-2 #要留j給i後面
        while i>=0:
            #若為左括 則在s中從i開始到len(s)-1計算dp[i]
            if s[i]=='(':
                j=i+1+dp[i+1]
                if j<len(s) and s[j]==')':
                    dp[i]=dp[i+1]+2 #+2為 s[i]與s[j]兩個可以湊一組
                    if j+1<len(s): #加上個紀錄點的值
                        dp[i]+=dp[j+1]
                res=max(res,dp[i])
            i-=1
        return res

result=Solution()
ans=result.longestValidParentheses(s="(()(()))")
print(ans)
'''
why???  j=i+1+dp[i+1]
找與i對應的新間格j:
在s中找從i + 1開始的有效括號匹配子串長度，即dp[i + 1]，
跳過這段已經記錄的括號子串，查看下一个字符，其下標即為j = i + 1 + dp[i + 1]

if j+1<len(s): dp[i]+=dp[j+1]
ex: s=") ( ) ( ) )"
   dp=[0,2,0,2,0,0]
dp[1]此2要再更新成2+2=4
'''