括号相关题目 LeetCode 20 有效括号 LeetCode 32 最长有效括号子串

括号序列相关题目

与括号序列有关的算法题目也较为常见，例如是否有效、有效深度、最长有效子序列等。这里对几道有代表性的题目做一下简单介绍。

括号序列的有效性判断

比如 LeetCode 20

这里我们看到题目对于有效的定义，关键就在于正确的顺序和同类型括号闭合。自然而然我们想到可以用栈的数据结构完成，将左括号入栈，遇到右括号就查看栈顶元素是否是同类型左括号，如果是的话就可以认为这个左括号以正确顺序用同类右括号闭合了；否则就没有正确闭合，那这个字符串就不是有效的。
代码如下：

bool isValid(string s) {
        if(s.empty()) return true;
        stack<char> st;
        for(int i=0;i<s.size();++i){
            if(s[i]=='('||s[i]=='['||s[i]=='{') st.push(s[i]);
            else{
                if(st.empty()) return false;
                if((s[i]==')'&&st.top()=='(') || (s[i]==']'&&st.top()=='[') || (s[i]=='}'&&st.top()=='{')){
                    st.pop();
                }
                else return false;
            }
        }
        return st.empty();
    }

当然如果只讨论一种括号，比如只包含’(’ ，’)'的字符串，我们不需要使用栈结构，只需要一个计数器就可以判断有效性：初始化计数器为0，遍历字符串，遇到左括号计数器+1，遇到右括号-1，如果过程出现了计数器小于0的情况，说明前面若干字符串存在右括号数量多于左括号，显然字符串无效。如果遍历结束计数器不是0，则全局左括号多于右括号，同样不合法。只有过程中计数器始终大于等于0且遍历结束时计数器等于0才是合法的。

最长有效括号子串

LeetCode 32 是这样一个问题：

给定一个只包含’(’ ，’)‘的字符串，整体未必是有效的，但是局部可能有效，那么有效部分子串最长的长度是多少。
我们知道有效的括号字符串，首先肯定得以右括号’)'结尾，同时多个有效括号子串相连同样构成了有效子串。
例如： (())()((()))是又有效的，但是可以看做是 (()), (), ((()))三个嵌套的有效括号连在一起的结果。

考虑动态规划的方法解决这一问题，同样讨论嵌套和连接两种情况：
构造数组dp，dp[i]就代表以第i个字符结尾的最长有效子串长度。
显然dp[0]和所有s[i]==’(‘的位置i，dp[i]均为0，也即以左括号结尾不可能有效，所以长度为0。
那么当以右括号’)‘结尾时，继续分类讨论。
首先研究嵌套的括号：
1· i位置时右括号’)’，前一个是左括号，显然这种情况i和i-1恰好构成一对有效括号，并且二者没有嵌套的成分，需要考虑i-1之前是不是有效子串，如果是需要加上，那么此时dp[i]至少为2；
2· i位置右括号，i-1同样也是右括号’)’，这种情况说明i位置可能处于嵌套括号的外层，需要判断能否在内层基础上形成有效括号，换言之，我们需要判断i-1右括号构成的有效子串之前一个位置是不是左括号，假设dp[i-1]=k，也就是以i-1的右括号结尾构成了一个长度为k的有效子串，也就是
从下标 i - k到 i - 1这k个元素构成了一个有效子串，那么再往前一个，就是i - k - 1这个位置，如果是左括号’(’，他就跟第i个位置的右括号’)'构成一对，那就实现了 i - k - 1到 i 这 k+2 个元素构成的嵌套有效子串。对于这种情况，dp[i]至少是dp[i-1]+2。但如果i - k - 1这个位置是右括号，那显然不能构成有效嵌套子串，那么dp[i]就是0.

对于嵌套的情况，上述两种情况是可以合并的，
首先我们记 pre = i - dp[i-1] - 1，那么对于i-1是左括号的情况（dp[i-1]=0），显然pre=i-1。当pre>=0(有效下标)并且 str[pre] == ‘(’ 的情况，dp[i]=dp[i-1]+2，就是嵌套情况下的子串长度。
这是因为，如果i-1是左括号，pre位置就是i-1且肯定满足str[pre] 为’('左括号，此时嵌套的有效子串长度为2，因为dp[i-1]是0，此时也等于 dp[i-1]+2；
如果i-1是右括号，不满足上述pre>=0(有效下标)并且 str[pre] = '('的 条件无法构成有效子串，不需讨论，满足条件的，嵌套的有效子串长度为 dp[i-1]+2。
显然只有存在嵌套（包括单层）有效子串才能讨论是否能跟前面的连成一个有效子串。连接部分情况较为简单，嵌套部分使得pre到i 构成了有效子串，这时只需要看以pre-1位置结尾的有效子串长度是多少，对于pre-1为右括号直接相加，pre-1若为左括号显然构不成连接的子串，但是因为左括号记录的长度都是0，所以仍然可以直接相加即可。综上，对于连接构成的子串，只需要在pre-1下标有效情况下，加上dp[pre-1]即可。
而最长的有效括号子串长度就是以每个元素结尾的有效长度中最长的那个。
C++代码如下：

int longestValidParentheses(string s) {
        if(s.empty()) return 0;
        int len=s.size(),maxl=0;
        vector<int>dp(len,0);
        for(int i=1;i<len;++i){
            if(s[i]==')'){
                int pre=i-1-dp[i-1];
                if(pre>=0 && s[pre]=='('){
                    dp[i]=dp[i-1]+2;
                    if(pre-1>=0) dp[i]+=dp[pre-1];
                }
            }
            maxl=max(maxl,dp[i]);
        }
        return maxl;
    }

构造DP数组，初始化所有元素为0，接下来如果以某个元素结尾长度为0就不在赋值。对于位置i处的右括号，且pre位置（i-1-dp[i-1]）是左括号的，存在嵌套的有效括号长度 dp[i-1]+2，再看pre-1有效的，存在连接的有效括号长度为dp[pre-1]，相加即可得到以i结尾的最长有效子串，遍历过程求最大值即可。