6.23 - hard - 6

32. Longest Valid Parentheses:

这题有几个难点,一是得想到用DP来做,我一开始用了stack做了一会,发现不行,要记录不同时候的状态,然后就想着用DP来做,结果折腾了半天,DP做出了一个TLE的版本。DP的想法是依次找,先找到相邻的 () 然后找(xx)中间有两个的,再分为两种情况 “(x” & “x)” 或者 “xx” 是valid,然后再找四个的,也就是(xxxx),分为这些情况(x&xxx) (xxx & x) xxxx这些如果是valid那么(xxxx)就是valid。不过最后还是TLE了,想法倒是没错,不过时间复杂度变n^2了。

(续。。。)
然后看了答案,发现解法还是用stack,简直是打脸。

想法是记录每个 "("的index到stack里,这个我也想到了,但是不忙着计算当前长度,等到所有的值全部loop 完了,再从stack里依次pop来计算两个pop出来之间的长度。还有一个条件就是如果stack为空,并且cur = ")"的话,把这个index也加到stack里去。

所以事实证明一开始的思路还是可以的,只是当要记录状态的时候,没想到如何用存在stack里的index来记录状态。

class Solution(object):
    def longestValidParentheses(self, s):
        """
        :type s: str
        :rtype: int
        """
        #一开始想的是stack,但是试了几下,发现要记录住之前的状态,然后想着用dp试试
        # dp[i][j] start with index i end with index j if it is valid
        # dp[i][j] is valid only if dp[i+1][j-1] is valid and s[i] == "(" and s[j] == ")"
        dp = [[False for _ in range(len(s))] for _ in range(len(s))]
        
        res = 0
        for i in range(len(s)):
            for j in range(len(s)):
                if i > j:
                    dp[i][j] = True
                if j - i == 1 and s[i] == "(" and s[j] == ")":
                    dp[i][j] = True

        l = 1
        while l < len(s):
            for i in range(len(s)-1):
                j = i+l
                if j < len(s):
                    if s[i] == "(" and s[j] == ")":
                        dp[i][j] = dp[i][j] or dp[i+1][j-1]
                        for k in range(i+1, j-1):
                            dp[i][j] = dp[i][j] or (dp[i][k] and dp[k+1][j])
                        if dp[i][j]:
                            res = max(res, j-i+1)
            l += 2
        
        return res
class Solution(object):
    def longestValidParentheses(self, s):
        """
        :type s: str
        :rtype: int
        """
        res = 0
        stack = []
        for i in range(len(s)):
            if s[i] == '(': 
                stack.append(i)
            else:
                if stack:
                    if s[stack[-1]] == '(':
                        stack.pop()
                    else:
                        stack.append(i)
                else:
                    stack.append(i)
                    
        if not stack:
            res = len(s)
        else:
            a = len(s)
            b = 0
            while stack:
                b = stack.pop()
                res = max(res, a-b-1)
                a = b
            res = max(res, a);
            
        return res
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 背景 一年多以前我在知乎上答了有关LeetCode的问题, 分享了一些自己做题目的经验。 张土汪:刷leetcod...
    土汪阅读 12,779评论 0 33
  • Android 自定义View的各种姿势1 Activity的显示之ViewRootImpl详解 Activity...
    passiontim阅读 173,624评论 25 708
  • LeetCode 刷题随手记 - 第一部分 前 256 题(非会员),仅算法题,的吐槽 https://leetc...
    蕾娜漢默阅读 17,950评论 2 36
  • 1. Java基础部分 基础部分的顺序:基本语法,类相关的语法,内部类的语法,继承相关的语法,异常的语法,线程的语...
    子非鱼_t_阅读 31,779评论 18 399
  • 前些日子,美国总统候选人辩论开战。这场90分钟的辩论估计吸引了超过1亿人观看,我们情不自禁感叹美国人对自己观点陈述...
    吴琼Cissy阅读 1,219评论 0 11