括号序列
定义一个合法括号序列（balanced bracket sequence）为仅由 
和 构成的字符串且：
- 空串 是一个合法括号序列。
- 如果 是合法括号序列，那么 也是合法括号序列。
- 如果 都是合法括号序列，那么 也是合法括号序列。
例如 是合法括号序列，而 不是。
有时候会有多种不同的括号，如 。这样的变种括号序列与朴素括号序列有相似的定义。
本文将会介绍与括号序列相关的经典问题。
注：英语中一般称左括号为 opening bracket，而右括号是 closing bracket。
判断是否合法
判断 是否为合法括号序列的经典方法是贪心思想。该算法同样适用于变种括号序列。
我们维护一个栈，对于 依次考虑：
- 如果 是右括号且栈非空且栈顶元素是 对应的左括号，就弹出栈顶元素。
- 若不满足上述条件，则将 压入栈中。
在遍历整个 后，若栈是空的，那么 就是合法括号序列，否则就不是。时间复杂度 。
合法括号序列计数
考虑求出长度为 的合法括号序列 的个数 。不妨枚举与 匹配的括号的位置，假设是 。它将整个序列又分成了两个更短的合法括号序列。因此
这同样是卡特兰数的递推式。也就是说 。
当然，对于变种合法括号序列的计数，方法是类似的。假设有 种不同类型的括号，那么有 。
字典序后继
给出合法的括号序列 ，我们要求出按字典序升序排序的长度为 的所有合法括号序列中，序列 的下一个合法括号序列。在本问题中，我们认为左括号的字典序小于右括号，且不考虑变种括号序列。
我们需要找到一个最大的 使得 是左括号。然后，将其变成右括号，并将 这部分重构一下。另外， 必须满足： 中左括号的数量 大于 右括号的数量。
不妨设当 变成右括号后， 中左括号比右括号多了 个。那么我们就让 的最后 个字符变成右括号，而 则用 的形式填充即可，因为这样填充的字典序最小。
该算法的时间复杂度是 。
参考实现
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;
}
|
字典序计算
给出合法的括号序列 ，我们要求出它的字典序排名。
考虑求出字典序比 小的括号序列 的个数。
不妨设 且 。显然 是左括号而 是右括号。枚举 （满足 为右括号），假设 中左括号比右括号多 个，那么相当于我们要统计长度为 且存在 个未匹配的右括号且不存在未匹配的左括号的括号序列的个数。
不妨设 表示长度为 且存在 个未匹配的右括号且不存在未匹配的左括号的括号序列的个数。
通过枚举括号序列第一个字符是什么，可以得到 的转移：。初始时 。其实 是 OEIS - A053121。
这样我们就可以 计算字典序了。
对于变种括号序列，方法是类似的，只不过我们需要对每个 考虑比它小的那些字符进行计算（在上述算法中因为不存在比左括号小的字符，所以我们只考虑了 为右括号的情况）。
另外，利用 数组，我们同样可以求出字典序排名为 的合法括号序列。
本页面主要译自博文 http://e-maxx.ru/algo/bracket_sequences 与其英文翻译版 Balanced bracket sequences。其中俄文版版权协议为 Public Domain + Leave a Link；英文版版权协议为 CC-BY-SA 4.0。
本页面最近更新：2023/2/18 07:57:07，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：Enter-tainer, sshwy, diauweb, ksyx, Xeonacid
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用