美文网首页
32.leetcode题目讲解(Python):最长有效括号

32.leetcode题目讲解(Python):最长有效括号

作者: 夏山闻汐 | 来源:发表于2018-11-06 13:45 被阅读56次

    题目:


    最长的有效括号

    解法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)

    相关文章

      网友评论

          本文标题:32.leetcode题目讲解(Python):最长有效括号

          本文链接:https://www.haomeiwen.com/subject/sgquxqtx.html