荐【小白用python刷Leetcode】32. 最长有效括号

程序员文章站 2022-09-13 22:42:42

32. 最长有效括号题目描述解题思路作为一个小白，表示只解出了最蠢的暴力解法。但是感觉暴力解法也并不是那么容易实现，题解代码：def kthSmallest(self, matrix: List[List[int]], k: int) -> int: # 归并排序 def guibing(s1,s2): # 我知道函数内套函数很蠢，但是我觉得面试时候面试官应该是会让手撕归并的，况且也不难是吧 res...

32. 最长有效括号

题目描述

荐
【小白用python刷Leetcode】32. 最长有效括号

解题思路

作为一个小白，表示只解出了最蠢的暴力解法。简单说就是分割子串，并逐一判断这个子串是否有效。但感觉暴力解法也并不是那么容易实现，因为当判断子串是否有效时，需要借助栈来实现。

具体来讲，由于要求的是最长有效括号，所以我的想法是子串的长度由长到短。先定义子串长度最长l = len(s)，然后对子串长度判断其是否为2的整数倍。因为如果这个子串是有效的，那么其长度一定为2的整数倍，换句话说这是子串有效的必要条件。然后判断当前长度的子串是否为有效的，若子串有效，由于我们是从最长的子串开始判断，所以当前子串的长度l就是最长有效括号的长度；若子串无效，由于有效子串总是成对出现，所以要在原先子串长度的基础上减2 (l = l - 2)，继续循环迭代。如果当子串长度一路减到0都没有找到有效子串，说明就没有有效子串，则返回0。

然后我们具体看怎么判断子串是否有效，我这里写了个ckeck(s)函数。具体来讲就是借助一个栈结构，遍历子串的每一个字符x，若x为左括号：则入栈；若x为右括号：进一步判断此时栈是否为空，若栈不为空，则栈顶元素出栈，表示当前栈顶的左括号和右括号可以组成一对有效括号；若栈为空，表示当前的右括号之前没有与之相匹配的左括号，直接返回False。在遍历完子串之后，如果栈不为空，表明栈内有未匹配到的左括号，一样是无效的子串。

题解代码：

def longestValidParentheses(self, s: str) -> int:
        def check(s):
            stack = []
            for x in s:
                if x == '(':
                    stack.append(x)
                elif stack != []:
                    stack.pop()
                else:
                    return False
            return stack == []
        
        l = len(s)
        if l % 2 != 0:
            l -= 1
        while l > 0:
            if l % 2 == 0:
                i = 0
                while (i+l) < len(s)+1:  # 注意这里是i+l而不是i+1
                    if check(s[i:i+l]):
                        return l
                    i += 1
            l -= 2
        return 0

运行结果：

由于是暴力解法，当然是超出了时间限制，227 / 230 个通过测试用例。。。

想想其实也正常，遍历得到子串的复杂度是O(n^3)，check的复杂度是O(n)，所以总的时间复杂度为O(n^3)，怎么可能不超时。

官方思路

思路一：栈

之前在暴力解法里虽然也用了栈，但是这个栈用的则高明的多。做法就是不再将字符压栈，入栈的是字符的位置（或者说是下标）。在说明具体过程之前，先明确一点：这个栈的栈底元素是上一个未匹配右括号的下标（先记住，至于为什么一会儿细说）。

具体过程是这样：遍历每个字符，如果当前字符是左括号，那么将当前字符的下标压栈。如果当前字符是右括号，则进一步判断栈此时长度是否为1，若不为1，表明栈顶的下标对应的左括号刚好和当前右括号配成一对，是有效的，那我们pop()出去。但是我们要的是最长，也就是需要累加之前的连续有效字符串的长度，那就用当前下标i减去pop()之后栈顶元素（就是上一个未匹配的左括号的下标），i - stack[-1] 这个值就是以当前右括号作为结尾的最长有效子字符串的长度。因为当前右括号的下标i减去的是上一个未匹配左括号的下标嘛。然后用简单的max函数筛选并更新总的最长有效子字符串的长度即可。但是如果栈的长度为1，还记得我们栈底的元素记录的是上一个未匹配右括号的下标，现在这个元素成为唯一的一个元素了，表明栈内并没有左括号与当前的右括号匹配，那这个当前的右括号不就是新的未匹配到的右括号吗！对上了，有木有！栈底元素是上一个未匹配右括号的下标！总是这样！所以我们要更新栈底元素到当前右括号的下标，即stack[0] = i。这也是为什么栈的栈底元素是上一个未匹配右括号的下标（重要的事情说三遍）。同时我们还解释了为什么判断栈的长度是否为1而不是别的数，因为要判断当前栈内是不是不存在左括号的下标，只存在栈底一个元素（右括号的下标）这种情况。有个额外的操作，就是初始化栈的时候要先加个-1，因为栈底元素是上一个未匹配右括号的下标，为让之后的代码正常运行特意加个。其实不一定是-1，是几都可以，因为只要保证栈底有元素就可以，-1比较有辨识度嘛。

题解代码（官方题解里是没有python版的哟）：

def longestValidParentheses(self, s: str) -> int:
        if not s:
            return 0
        
        res = 0  # 记录总的最长有效子字符串
        stack = [-1]  # 初始预设栈底元素
        for i in range(len(s)):
            if s[i] == '(':
                stack.append(i)  # 压入的是下标
            else:
                if len(stack) != 1:  # 判断是否栈内只有一个栈底元素
                    stack.pop()  # 先出栈，再更新res
                    res = max(res, i-stack[-1])  
                else:
                    stack[0] = i  # 更新栈底元素
        return res

这样子的时间复杂度就比较优秀了，是O(n)，空间复杂度同样也是O(n)。

运行结果：

荐
【小白用python刷Leetcode】32. 最长有效括号

思路二：动态规划

动态规划对于我来说可真是太头疼了，就连题解看得都很吃力呢。谁让咱菜呢。。。

具体来看，我们创建一个状态列表dp，其内存储的是以当前位字符作为结尾的最长有效子串的长度，长度为字符串的长度，并将列表内所有元素置0初始化。一个有效的子串，其结尾一定不可能是左括号，所以在我们遍历字符串的时候，遇到 '(' 直接将相应位置上的列表元素dp[i]置0即可。又由于dp初始化全部置0，所以在遍历时遇到左括号的话，直接跳过这个位置就好。换句话说，在遍历字符串时，我们只有遇到右括号才做出操作。

首先，我们先考虑初条件，其实也就是dp[0]的值。显然以s[0]作为结尾的子串只有s[0]本身，无论s[0]是什么，都不可能有效，所以dp[0]一定是0，这就是初条件。而由于我们在预设dp时将其全部置0了，所以相当于初条件我们已经设置过了。之后的遍历，从i=1开始就可以了。

其次，考虑状态转移方程。之前我们提到了在遍历过程中，遇到右括号才操作，那么这个操作到底是什么。动态规划嘛，我们要做的就是不断更新状态列表dp，具体点就是要确定dp[i]。根据dp列表的定义，我们要找到以当前右括号作为结尾的最长有效括号的长度。那么当前右括号首先必须是有效括号的一部分，要想有效，必要条件就是在之前的字符串中可以找到'('字符与其匹配。那么这个之前的字符'('是有多前，也就是这个'('应该出现在字符串s的哪个位置上才是与当前右括号匹配的那个'('呢？答案是(i-dp[i-1]-1)这个位置上。因为我们要考虑这一对括号之间还夹了其他有效的子串，要将这些位置跳过，跳多远？就是跳dp[i-1]，因为dp[i-1]记录了当前括号对内部，最长的有效子串长度，把这个跳过不就完了，所以(i-dp[i-1])就跳过去了。那为啥还要-1呢，因为(i-dp[i-1])跳过的是内部子串，跳过去以后的落点恰好是内部有效子串的开头位置，而不是我们要找的那个与当前')'匹配的之前的'('的位置，再向前走一位才是，所以就变成了(i-dp[i-1]-1)。那我们这是考虑了这一对括号中间有东西夹着，加入这一对括号内是空的呢？其实还是(i-dp[i-1]-1)。因为这一对括号是空的，即为'()'，是连着的。那dp[i-1]就是0，因为s[i-1]就是那个左括号嘛。(i-dp[i-1]-1)变为(i-1)，不还是指向前一位左括号，没毛病。现在找到了与当前')'匹配的'('的位置，那我们必须保证这个位置上就是'('，不然如果这个位置被另一个')'占据了，当前右括号不还是无效的嘛。所以就要判断 s[i-dp[i-1]-1] == '(' 才会操作，也就是满足当前右括号是有效这一前提。

在此基础下再考虑dp[i]和谁有关呢，或者说谁可以决定dp[i]的取值。有三点：1. 当前这一对有效括号的长度，很显然是2，一左一右嘛；2. 在这一对有效括号内部，最长有效括号的长度，即dp[i-1]；3. 在这一对有效括号之前，已有的最长有效括号的长度，为dp[i-dp[i-1]-1-1]，即dp[i-dp[i-1]-2]。这里为啥又多减了一个1呢？因为刚才提到(i-dp[i-1]-1)位置上是我们确定的与当前右括号匹配的'('，那现在我们要找的是这一对之前，可不是得再向前跳一位才能恰好完全将当前有效子串都跳过去嘛。将这三点加和，就是以当前右括号作为结尾的最长有效括号的长度dp[i]。至此状态转移方程可以确定：dp[i] = 2 + dp[i-1] + dp[i-dp[i-1]-2]。此外，还要考虑每个下标的有效性问题，别超了长度边界。因为i是由1开始遍历增长的，所以dp[i-1]的下标(i-1)一定不会超出边界，但是(i-dp[i-1]-2)有可能会超出，当 (i-dp[i-1]-2) < 0 时，dp数组中是没有dp[i-dp[i-1]-2]这个元素的（虽然语法上没错，因为在python中下标为-n标示倒数第n个位置上的元素），那我们将这一项直接置0就好。即当(i-dp[i-1]-2) < 0 时，状态转移方程为dp[i] = 2 + dp[i-1]，其它不变仍是刚才那个状态转移方程。

那动态规划的过程大抵就是这样，最后我们在dp中挑个最大的返回就行，即 return max(dp)。

题解代码（官方题解里这种解法也是没有python版的，而且我自以为写得还挺简洁）：

def longestValidParentheses(self, s: str) -> int:
        if not s:
            return 0

        dp = [0 for _ in range(len(s))]
        for i in range(1, len(s)):
            if s[i] == ')':  # 有效的大前提
                if i-dp[i-1]-1 >= 0 and s[i-dp[i-1]-1] == '(':  # 前一个判断条件只是为了保证不超边界
                    if i-dp[i-1]-2 >= 0:  # 仍然是为了不超边界而分开考虑
                        dp[i] = 2 + dp[i-1] + dp[i-dp[i-1]-2]
                    else:
                        dp[i] = 2 + dp[i-1]
        return max(dp)

动态规划解法的效率也很优秀，和上一种解法一样，时间和空间复杂度都为O(n)。

运行结果：

荐
【小白用python刷Leetcode】32. 最长有效括号