最长的括号子串

2021年11月26日 阅读数:2
这篇文章主要向大家介绍最长的括号子串,主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。

最长的括号子串

问题描述

给出一个长度为 n 的,仅包含字符 '(' 和 ')' 的字符串,计算最长的格式正确的括号子串的长度。算法

示例:数组

输入:"(())"app

输出:4code

解析:对于"(())"来讲,最长格式正确的子串是"(())",因此为4。字符串

分析问题

对于括号匹配问题,最直观的想法就是采用栈来求解。因此,咱们也能够采用栈来求解这道题。具体来讲,咱们在遍历给定字符串的过程当中,须要始终保证栈底元素为当前已经遍历过的元素中,最后一个没有被匹配的右括号的下标,栈中的其它元素维护左括号的下标。io

  1. 若是遇到的是左括号‘(’,咱们就把它的下标放入栈中;
  2. 若是遇到的是右括号‘)’,此时有两种状况;
    • 若是此时栈为空,说明当前的右括号是没有被匹配的右括号,
    • 若是此时栈不为空,右括号的下标减去栈顶元素即为「以该右括号为结尾的最长有效括号的长度」,而后用它来更新最大值便可。

这里须要注意一点,由于一开始栈为空,若是此时第一个字符为左括号时,咱们会将其对应的下标放入栈中,这样就不知足栈底始终保存的是最后一个没有被匹配的右括号的下标这个条件,为了保证该条件成立,咱们在开始时须要往栈中放入一个元素-1。class

咱们以“())(())”为例,来看一下执行过程。object

image-20211029222525672

image-20211029222544254

image-20211029222628761

image-20211029222646218

下面咱们来看一下代码实现。遍历

class Solution(object):
    def longestValidParentheses(self, s):
        stack=[]
        n=len(s)
        stack.append(-1)
        maxlen=0
        for i in range(0,n):
            #若是是左括号,将其对应的下标加入栈中
            if s[i]=='(':
                stack.append(i)
            else:
                #若是是右括号,栈顶元素pop出去
                stack.pop()
                if not stack:
                    stack.append(i)
                else:
                    maxlen = max(maxlen, i - stack[-1])

        return maxlen

该算法的时间复杂度和空间复杂度都是O(n)。im

动态规划解法

对于求最优解问题,咱们通常首先须要考虑的就是动态规划的解法。显然,求最长的括号子串是最优解问题,全部咱们也能够采用动态规划的思想来求解。

首先咱们定义dp[i]表示如下标i字符结尾的最长有效括号的长度,初始时数组dp全为0。对于有效的括号子串来讲,显然是以字符‘)’结尾的,所以咱们能够知道以‘(’结尾的子串对应的dp值必然为0,因此咱们只须要求解字符‘)’在dp数组中对应位置的值便可。

咱们从前日后遍历字符串s。

  1. 若是s[i]=‘)’且 s[i-1]=‘(’,也就是字符串是 “....()....()....”的形式,那么咱们能够得出状态转移方程为dp[i] = dp[i-2] + 2。

  2. 若是s[i]=‘)’且 s[i-1]=‘)’,也就是字符串是“.........))...”的形式,此时若是s[i-dp[i-1]-1] = ‘(’,那么

    dp[i] = dp[i-1] + 2 + dp[i - dp[i-1] - 2]

    解释:若是 s[i-1] 对应的 ‘)’ 是有效子字符串的一部分,咱们假设为sub1,那么它的的长度为dp[i-1],若是s[i]对应的‘)’是一个更长子字符串的一部分,那么必定有一个对应的‘(’与子相匹配,且它的位置在sub1的以前。若是sub1的前面刚好是‘(’,即“ (sub1) ”的形式,那么dp[i]=dp[i-1] + 2 + dp[i-dp[i-1] - 2] ,其中dp[i-dp[i-1] - 2] 表示字符串“(sub1)”前面的有效子串的长度,咱们须要加上。

image-20211029222732045

image-20211029222748680

image-20211029222807374

image-20211029222823818

下面咱们来看一下代码的实现。

class Solution(object):
    def longestValidParentheses(self, s):
        maxlen=0
        n=len(s)
        dp=[0] * n
        for i in range(1,n):
            #若是s[i]==')'而且s[i-1]=='(',那么dp[i] = dp[i-2]+2
            if s[i]==')':
                if s[i-1]=='(':
                    dp[i] = 2 + (dp[i-2] if i>=2 else 0)
                elif i-dp[i-1]-1 >= 0 and s[i-dp[i-1]-1]=='(':
                    dp[i] = dp[i - 1] + 2 + (dp[i - dp[i - 1] - 2] if i-dp[i-1]>=2 else 0)

                maxlen=max(maxlen,dp[i])
        return maxlen

该算法的时间复杂度是O(n),空间复杂度也是O(n)。