32.leetcode题目讲解（Python）：最长有效括号

题目：

最长的有效括号

解法1：通过使用栈来实现。遍历字符串，如果字符等于 "("，将该字符的索引放入栈中。如果字符等于")"，首先判断栈是否为空，若为空，直接将其索引放入栈中。如果栈不为空，那查看栈顶元素是否为 "("，如果是，进行pop()操作，当前长度等于 当前 “)” 的索引减去pop()操作后的栈顶元素（如果pop()后栈为空，那么当前长度等于索引+1）。

特别注意：栈是否为空

参考代码如下：

class Solution:
    def longestValidParentheses(self, s):
        """
        :type s: str
        :rtype: int
        """

        if len(s) == 0 or len(s) == 1:
            return 0

        stack = []
        j = 0
        max_len = 0

        while j < len(s):
            if s[j] == "(":
                stack.append(j)

            if s[j] == ")":
                if len(stack) and s[stack[-1]] == "(":
                    stack.pop()
                    if len(stack):
                        lens = j - stack[-1]
                        if lens > max_len:
                            max_len = lens
                    else:
                        lens = j + 1
                        if lens > max_len:
                            max_len = lens

                else:
                    stack.append(j)
            j += 1

        return max_len

解法2：动态规划（待更新）
动态规划的思路是，我们用一个list：dp 来记录字符串s中第i个元素的有效匹配长度。
当前字符为“)”时，才有可能出现匹配，所以我们关注两种情况：“()”和“))”

1. “()”:

 dp[i] = dp[i - 2] + 2 #直接在历史匹配数上增加2

2.“))”:

 if i - dp[i-1] - 1 >= 0: # 确保没有超出索引
                    if s[i - dp[i - 1] - 1] == "(":  #最后一个“)”是否有匹配
                        dp[i] = dp[i - 1] + dp[i - dp[i - 1] - 2] + 2 # 在历史匹配上增加2

完整代码如下：

class Solution:
    def longestValidParentheses(self, s):
        """
        :type s: str
        :rtype: int
        """

        dp = []
        lens = len(s)

        if lens < 2:
            return 0


        # initialize dp lisSt
        j = 0
        while j < lens:
            dp.append(0)
            j += 1

        i = 1
        while i < lens:
            if s[i] == ")" and s[i - 1] == "(":
                dp[i] = dp[i - 2] + 2

            if s[i] == s[i - 1] == ")":
                if i - dp[i-1] - 1 >= 0:
                    if s[i - dp[i - 1] - 1] == "(":
                        dp[i] = dp[i - 1] + dp[i - dp[i - 1] - 2] + 2
            i += 1

        return max(dp)

---

源码地址：
https://github.com/jediL/LeetCodeByPython

其它题目：[leetcode题目答案讲解汇总（Python版 持续更新）]
(https://www.jianshu.com/p/60b5241ca28e)

ps：如果您有好的建议，欢迎交流 :-D，
也欢迎访问我的个人博客 苔原带 (www.tundrazone.com)