括号最常见的用途是在表达式中人为地确定优先级。 即使是最简单的编译器在lexer和parser中都需要对括号做特殊处理。

当我们考虑只由括号组成的字符串时，可以产生一些有趣的算法题，在这篇博客中我想总结我遇到的一些关于括号序列的算法题，希望之后不要被类似的题目难到。

 

leetcode20, 判断括号序列是否合法。

只要学过最简单的数据结构，都知道用栈来处理这个问题。可以在时间空间O(n)的复杂度下很高效地解决。

如果我们把问题简化一下，字符串只包含两种括号字符，即只包含'('或')', 我们有没有更高效的算法呢？

答案是这种情况下，我们可以把空间复杂度优化到O(1), 准确的说，除了已经给出的字符串，我们只需要一个额外的整数计数器即可。

我们设一个计数器cnt=0, 从左到右遍历字符串， 遇到'(' cnt++, 遇到')' cnt-- ， 如果在任意时刻， cnt<0 ,则它必不合法。 如果最后cnt==0 则合法。

这背后的数学证明就不给出了，稍微思考一下就可以弄明白。

 

以上的解法让我们可以更加抽象的理解括号序列。 我们可以将一个括号序列 "())" 转化为数字序列(1,-1,-1)。 只要这个数字序列的和为0，且前缀和不为负，就是合法的括号序列。

在这个基础上，我们又可以问一个组合数学的问题， 给定n对括号，可以产生多少个合法的括号序列？

答案是一个特殊计数序列 Catalan数。 Catalan数可以用递推公式和通项公式高效求解，更多关于Catalan数的知识就不在这里给出了。

 

leetcode32 给定一个括号序列，找到其中合法的最长括号序列的长度。

用上述提到的计数器方法， 从左到右遍历字符串， 当cnt<0时，括号序列被割断，我们必须重新开始记录合法的长度， 当cnt=0时以当前长度更新最长长度。

按照上述方法只遍历一次，会错过“(()”这样的括号， 因为cnt总不为0. 避免这样的错误只需要反向类似地遍历一次即可。

 

leetcode2116 给定一个括号序列，允许修改其中部分位置的字符，判断是否可能修改成一个合法的括号序列。

首先，长度必须是偶数，不然不可能合法。

之后，我们按照leetcode32的思路做双向遍历。 向右遍历时，把可改的括号都当作左括号，也就是遇到可改的或者左括号 cnt++, 遇到不可改的右括号cnt--， 遇到cnt<0 则无法修改为合法的括号序列。

反向遍历的思路是类似的。 Go代码如下

func canBeValid(s string, locked string) bool {
    if len(s)%2 != 0 {return false}
    cnt:= 0
    for i:=0;i<len(s);i++{
        if locked[i] == '0' || s[i]=='(' {cnt++;continue}
        cnt-- 
        if cnt<0 {return false}
    }
    cnt = 0
    for i:=len(s)-1;i>=0;i--{
        if locked[i] == '0' || s[i]==')' {cnt++;continue}
        cnt-- 
        if cnt<0 {return false}
    }
    return true
}