题解 | #最长的括号子串#

题目主要信息：

• 一个长度为$nn$的仅包含左右括号的字符串
• 计算最长的格式正确的括号子串的长度

举一反三：

学习完本题的思路你可以解决如下题目：

BM65 最长公共子序列(二)

BM66.最长公共子串

BM71.最长上升子序列(一)

BM73 最长回文子串

BM75 编辑距离(一)

BM76 正则表达式匹配

方法一：栈（推荐使用）

知识点：栈

栈是一种仅支持在表尾进行插入和删除操作的线性表，这一端被称为栈顶，另一端被称为栈底。元素入栈指的是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；元素出栈指的是从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。

思路：

因为括号需要一一匹配，而且先来的左括号，只能匹配后面的右括号，因此可以考虑使用栈的先进后出功能，使括号匹配。

具体做法：

• step 1：可以使用栈来记录左括号下标。
• step 2：遍历字符串，左括号入栈，每次遇到右括号则弹出左括号的下标。
• step 3：然后长度则更新为当前下标与栈顶下标的距离。
• step 4：遇到不符合的括号，可能会使栈为空，因此需要使用start记录上一次结束的位置，这样用当前下标减去start即可获取长度，即得到子串。
• step 5：循环中最后维护子串长度最大值。

图示：

Java实现代码：

import java.util.*;
public class Solution {
    public int longestValidParentheses (String s) {
        int res = 0;
        //记录上一次连续括号结束的位置
        int start = -1; 
        Stack<Integer> st = new Stack<Integer>();
        for(int i = 0; i < s.length(); i++){
            //左括号入栈
            if(s.charAt(i) == '(') 
                st.push(i);
            //右括号
            else{ 
                //如果右括号时栈为空，不合法，设置为结束位置
                if(st.isEmpty()) 
                    start = i;
                else{
                    //弹出左括号
                    st.pop(); 
                    //栈中还有左括号，说明右括号不够，减去栈顶位置就是长度
                    if(!st.empty()) 
                        res = Math.max(res, i - st.peek());
                    //栈中没有括号，说明左右括号行号，减去上一次结束的位置就是长度
                    else 
                        res = Math.max(res, i - start);
                }
            }
        }
        return res;
    }
}

C++实现代码：

class Solution {
public:
    int longestValidParentheses(string s) {
        int res = 0;
        //记录上一次连续括号结束的位置
        int start = -1; 
        stack<int> st;
        for(int i = 0; i < s.length(); i++){
            //左括号入栈
            if(s[i] == '(') 
                st.push(i);
            //右括号
            else{ 
                //如果右括号时栈为空，不合法，设置为结束位置
                if(st.empty()) 
                    start = i;
                else{
                    //弹出左括号
                    st.pop(); 
                    //栈中还有左括号，说明右括号不够，减去栈顶位置就是长度
                    if(!st.empty()) 
                        res = max(res, i - st.top());
                    //栈中没有括号，说明左右括号行号，减去上一次结束的位置就是长度
                    else 
                        res = max(res, i - start);
                }
            }
        }
        return res;
    }
};

Python代码实现：

class Solution:
    def longestValidParentheses(self , s: str) -> int:
        res = 0
        #记录上一次连续括号结束的位置
        start = -1 
        st = []
        for i in range(len(s)):
            #左括号入栈
            if s[i] == '(': 
                st.append(i)
            #右括号
            else: 
                #如果右括号时栈为空，不合法，设置为结束位置
                if len(st) == 0: 
                    start = i
                else:
                    #弹出左括号
                    st.pop()
                    #栈中还有左括号，说明右括号不够，减去栈顶位置就是长度
                    if len(st) != 0: 
                        res = max(res, i - st[-1])
                    #栈中没有括号，说明左右括号行号，减去上一次结束的位置就是长度
                    else: 
                        res = max(res, i - start)
        return res

复杂度分析：

• 时间复杂度：$O(n)O(n)$，其中$nn$为字符串长度，遍历整个字符串
• 空间复杂度：$O(n)O(n)$，最坏全是左括号，栈的大小为$nn$

方法二：动态规划（扩展思路）

知识点：动态规划

动态规划算法的基本思想是：将待求解的问题分解成若干个相互联系的子问题，先求解子问题，然后从这些子问题的解得到原问题的解；对于重复出现的子问题，只在第一次遇到的时候对它进行求解，并把答案保存起来，让以后再次遇到时直接引用答案，不必重新求解。动态规划算法将问题的解决方案视为一系列决策的结果

思路：

像这种子串长度的题，一般都涉及状态转移，可以用动态规划的方式。

具体做法：

• step 1：用$dp[i]dp[i]$表示以下标为i的字符为结束点的最长合法括号长度。

• step 2：很明显知道左括号不能做结尾，因此但是左括号都是$dp[i]=0dp[i]=0$。

• step 3：我们遍历字符串，因为第一位不管是左括号还是右括号dp数组都是0，因此跳过，后续只查看右括号的情况，右括号有两种情况：

  • 情况一：

  如图所示，左括号隔壁是右括号，那么合法括号需要增加2，可能是这一对括号之前的基础上加，也可能这一对就是起点，因此转移公式为：$dp[i]=(i>=2?dp[i-2]:0)+2dp[i]\; =\; (i\; >=\; 2\; ?\; dp[i\; -\; 2]\; :\; 0)\; +\; 2$

  • 情况二：

  如图所示，与该右括号匹配的左括号不在自己旁边，而是它前一个合法序列之前，因此通过下标减去它前一个的合法序列长度即可得到最前面匹配的左括号，因此转移公式为：$dp[i]=(i-dp[i-1]>1?dp[i-dp[i-1]-2]:0)+dp[i-1]+2dp[i]\; =\; (i\; -\; dp[i\; -\; 1]\; >\; 1\; ?\; dp[i\; -\; dp[i\; -\; 1]\; -\; 2]\; :\; 0)\; +\; dp[i\; -\; 1]\; +\; 2$

• step 4：每次检查完维护最大值即可。

Java实现代码：

import java.util.*;
public class Solution {
    public int longestValidParentheses (String s) {
        int res = 0;
        //长度为0的串或者空串，返回0
        if(s.length() == 0 || s == null) 
            return res;
        //dp[i]表示以下标为i的字符为结束点的最长合法括号长度
        int[] dp = new int[s.length()];  
        //第一位不管是左括号还是右括号都是0，因此不用管
        for(int i = 1; i < s.length(); i++){ 
            //取到左括号记为0，有右括号才合法
            if(s.charAt(i) == ')'){ 
                //如果该右括号前一位就是左括号
                if(s.charAt(i - 1) == '(') 
                    //计数+
                    dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2; 2
                //找到这一段连续合法括号序列前第一个左括号做匹配
                else if(i - dp[i - 1] > 0 && s.charAt(i - dp[i - 1] - 1) == '(') 
                    dp[i] = (i - dp[i - 1] > 1 ? dp[i - dp[i - 1] - 2] : 0) + dp[i - 1] + 2;
            }
            //维护最大值
            res = Math.max(res, dp[i]); 
        }
        return res;
    }
}

C++实现代码：

class Solution {
public:
    int longestValidParentheses(string s) {
        int res = 0;
        //长度为0的串，返回0
        if(s.length() == 0) 
            return res;
        //dp[i]表示以下标为i的字符为结束点的最长合法括号长度
        vector<int> dp(s.length(), 0); 
        //第一位不管是左括号还是右括号都是0，因此不用管
        for(int i = 1; i < s.length(); i++){ 
            //取到左括号记为0，有右括号才合法
            if(s[i] == ')'){ 
                //如果该右括号前一位就是左括号
                if(s[i - 1] == '(') 
                    //计数+2
                    dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2; 
                //找到这一段连续合法括号序列前第一个左括号做匹配
                else if(i - dp[i - 1] > 0 && s[i - dp[i - 1] - 1] == '(') 
                    dp[i] = (i - dp[i - 1] > 1 ? dp[i - dp[i - 1] - 2] : 0) + dp[i - 1] + 2;
            }
            //维护最大值
            res = max(res, dp[i]); 
        }
        return res;
    }
};

Python代码实现：

class Solution:
    def longestValidParentheses(self , s: str) -> int:
        res = 0
        #长度为0的串，返回0
        if len(s) == 0: 
            return res
        #dp[i]表示以下标为i的字符为结束点的最长合法括号长度
        dp = [0 for i in range(len(s))] 
        #第一位不管是左括号还是右括号都是0，因此不用管
        for i in range(1, len(s)): 
            #取到左括号记为0，有右括号才合法
            if s[i] == ')': 
                #如果该右括号前一位就是左括号
                if s[i - 1] == '(': 
                    #计数+2
                    if i >= 2: 
                        dp[i] = dp[i - 2] + 2
                    else:
                        dp[i] = 2 
                #找到这一段连续合法括号序列前第一个左括号做匹配
                elif i - dp[i - 1] > 0 and s[i - dp[i - 1] - 1] == '(':
                    if i - dp[i - 1] > 1:
                        dp[i] = dp[i - dp[i - 1] - 2] + dp[i - 1] + 2
                    else:
                        dp[i] = dp[i - 1] + 2
            #维护最大值
            res = max(res, dp[i]) 
        return res

复杂度分析：

• 时间复杂度：$O(n)O(n)$，其中$nn$为字符串长度，遍历一次字符串
• 空间复杂度：$O(n)O(n)$，动态规划辅助数组的长度为$nn$