括号序列

定义一个合法括号序列(balanced bracket sequence)为仅由 ( ) 构成的字符串且:

  • 空串 \varepsilon 是一个合法括号序列。
  • 如果 s 是合法括号序列,那么 (s) 也是合法括号序列。
  • 如果 s,t 都是合法括号序列,那么 st 也是合法括号序列。

例如 (())() 是合法括号序列,而 )() 不是。

有时候会有多种不同的括号,如 [()]\{\} 。这样的变种括号序列与朴素括号序列有相似的定义。

本文将会介绍与括号序列相关的经典问题。

注:英语中一般称左括号为 opening bracket,而右括号是 closing bracket。

判断是否合法

判断 s 是否为合法括号序列的经典方法是贪心思想。该算法同样适用于变种括号序列。

我们维护一个栈,对于 i=1,2,\ldots,|s| 依次考虑:

  • 如果 s_i 是右括号且栈非空且栈顶元素是 s_i 对应的左括号,就弹出栈顶元素。
  • 若不满足上述条件,则将 s_i 圧入栈中。

在遍历整个 s 后,若栈是空的,那么 s 就是合法括号序列,否则就不是。时间复杂度 O(n)

合法括号序列计数

考虑求出长度为 2n 的合法括号序列 s 的个数 f_n 。不妨枚举与 s_1 匹配的括号的位置,假设是 2i+2 。它将整个序列又分成了两个更短的合法括号序列。因此

f_n=\sum_{i=0}^{n-1}f_if_{n-i-1}

这同样是卡特兰数的递推式。也就是说 f_n=\frac{1}{n+1}\binom{2n}{n}

当然,对于变种合法括号序列的计数,方法是类似的。假设有 k 种不同类型的括号,那么有 f'_n=\frac{1}{n+1}\binom{2n}{n}k^n

字典序后继

给出合法的括号序列 s ,我们要求出按字典序升序排序的长度为 |s| 的所有合法括号序列中,序列 s 的下一个合法括号序列。在本问题中,我们认为左括号的字典序小于右括号,且不考虑变种括号序列。

我们需要找到一个最大的 i 使得 s_i 是左括号。然后,将其变成右括号,并将 s[i+1,|s|] 这部分重构一下。另外, i 必须满足: s[1,i-1] 中左括号的数量 大于 右括号的数量。

不妨设当 s_i 变成右括号后, s[1,i] 中左括号比右括号多了 k 个。那么我们就让 s 的最后 k 个字符变成右括号,而 s[i+1,|s|-k] 则用 ((\dots(())\dots)) 的形式填充即可,因为这样填充的字典序最小。

该算法的时间复杂度是 O(n)

参考实现
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
bool next_balanced_sequence(string& s) {
  int n = s.size();
  int depth = 0;
  for (int i = n - 1; i >= 0; i--) {
    if (s[i] == '(')
      depth--;
    else
      depth++;

    if (s[i] == '(' && depth > 0) {
      depth--;
      int open = (n - i - 1 - depth) / 2;
      int close = n - i - 1 - open;
      string next =
          s.substr(0, i) + ')' + string(open, '(') + string(close, ')');
      s.swap(next);
      return true;
    }
  }
  return false;
}

字典序计算

给出合法的括号序列 s ,我们要求出它的字典序排名。

考虑求出字典序比 s 小的括号序列 p 的个数。

不妨设 p_i<s_i \forall 1\le j<i,p_j=s_i 。显然 p_i 是左括号而 s_i 是右括号。枚举 i (满足 s_i 为右括号),假设 p[1,i] 中左括号比右括号多 k 个,那么相当于我们要统计长度为 |s|-i 且存在 k 个未匹配的右括号且不存在未匹配的左括号的括号序列的个数。

不妨设 f(i,j) 表示长度为 i 且存在 j 个未匹配的右括号且不存在未匹配的左括号的括号序列的个数。

通过枚举括号序列第一个字符是什么,可以得到 f 的转移: f(i,j) = f(i-1,j-1)+f(i-1,j+1) 。初始时 f(0,0)=1 。其实 f OEIS - A053121

这样我们就可以 O(|s|^2) 计算字典序了。

对于变种括号序列,方法是类似的,只不过我们需要对每个 s_i 考虑比它小的那些字符进行计算(在上述算法中因为不存在比左括号小的字符,所以我们只考虑了 s_i 为右括号的情况)。

另外,利用 f 数组,我们同样可以求出字典序排名为 k 的合法括号序列。

本页面主要译自博文 http://e-maxx.ru/algo/bracket_sequences 与其英文翻译版 Balanced bracket sequences。其中俄文版版权协议为 Public Domain + Leave a Link;英文版版权协议为 CC-BY-SA 4.0。


评论