[Leetcode][python]Longest Valid Parentheses

痛定思痛。 2022-06-09 13:46 134阅读 0赞

## 题目大意 ##

找出一个只包含"(“和”)"的字符串中最长的有效子字符串的长度。有效的意思是指该子字符串中的括号都能正确匹配。

## 解题思路 ##

[https://shenjie1993.gitbooks.io/leetcode-python/032 Longest Valid Parentheses.html][https_shenjie1993.gitbooks.io_leetcode-python_032 Longest Valid Parentheses.html]  
采用了**动态规划**，dp\[i\]表示以i为子字符串末尾时的最大长度，最后的结果就是dp中的最大值。如果不是空字符串，则dp\[0\]=0，因为一个括号肯定无法正确匹配。递推关系是:

) ( ) ( ( ) ) )
    0 0 2 0 0 2 6 0

## 代码 ##

### 动态规划 ###

![这里写图片描述][70]

class Solution(object):
        def longestValidParentheses(self, s):
            """
            :type s: str
            :rtype: int
            """
            if not s:
                return 0
            length = len(s)
            dp = [0 for __ in range(length)]  # [0,0,0,0,0,0]
            
            for i in range(1, length):
                if s[i] == ")":
                    j = i - 1 - dp[i - 1]  # 直接去查找前面的第n位，位移过了dp[i-1]位已经匹配的
                    if j >= 0 and s[j] == "(":  # 如果那位是‘（’则可以总数多+2
                        dp[i] = dp[i - 1] + 2
                        if j - 1 >= 0:
                            dp[i] += dp[j - 1]  # 重点，会把这次匹配之前的加进去，例如（）（（））
            return max(dp)

### 栈 ###

这题还可以用栈来解决，重点是栈内存储的是索引号，效率比动态规划好一些。  
![这里写图片描述][70 1]

class Solution(object):
        def longestValidParentheses(self, s):
            """
            :type s: str
            :rtype: int
            """
            maxlen = 0
            stack = []
            last = -1
            for i in range(len(s)):
                if s[i]=='(':
                    stack.append(i)     # push the INDEX into the stack!!!!
                else:
                    if stack == []:
                        last = i
                    else:
                        stack.pop()
                        if stack == []:
                            maxlen = max(maxlen, i-last)
                        else:
                            # print i, stack[len(stack)-1]
                            maxlen = max(maxlen, i-stack[len(stack)-1])
            return maxlen

## 总结 ##

[https_shenjie1993.gitbooks.io_leetcode-python_032 Longest Valid Parentheses.html]: https://shenjie1993.gitbooks.io/leetcode-python/032%20Longest%20Valid%20Parentheses.html
[70]: /images/20220609/f5bdbef93b1b4a1f99f3b7e8da85ce64.png
[70 1]: /images/20220609/85c8382337134f4eb056247256042399.png