0020. Valid Parentheses
=======================
题目信息
--------
:题号: 0020. 有效的括号
:难度: Easy
:主题: 字符串、栈、括号匹配
:原题: `LeetCode 0020 `_
:重点: 从反复消去最内层配对,推导到用栈直接维护尚未完成的闭合顺序
题目重述
--------
给定一个只包含 ``(``、``)``、``[``、``]``、``{``、``}`` 的字符串 ``s``,判断整个字符串是否为有效括号串。
有效括号串同时满足以下条件:
* 每个左括号都由同类型的右括号闭合;
* 每个右括号左侧都存在尚未闭合的对应左括号;
* 后出现的内层左括号必须先闭合,不能与外层括号交叉配对。
字符串长度位于 ``[1, 10^4]``。题目只要求返回是否合法,不需要给出具体配对位置。
自建示例
--------
* 正确嵌套:``s = "([]{})"``,内层 ``[]``、``{}`` 先闭合,返回 ``true``;
* 正确并列:``s = "()[]{}"``,三组括号依次完成,返回 ``true``;
* 类型交叉:``s = "([)]"``,读到 ``)`` 时最近未闭合的是 ``[``,返回 ``false``;
* 多余右括号:``s = "())"``,最后一个 ``)`` 没有可匹配的左括号,返回 ``false``;
* 缺少右括号:``s = "(([]"``,扫描结束后仍有两个左括号未闭合,返回 ``false``;
* 最小规模:``s = "("``,长度为奇数且无法形成完整配对,返回 ``false``。
C++ 实现
--------
.. code-block:: cpp
#include
#include
class Solution {
private:
bool isPair(char left, char right) {
return (left == '(' && right == ')') ||
(left == '[' && right == ']') ||
(left == '{' && right == '}');
}
bool eraseOneInnermostPair(std::string& text) {
for (int index = 0; index + 1 < static_cast(text.size()); ++index) {
if (isPair(text[index], text[index + 1])) {
text.erase(index, 2);
return true;
}
}
return false;
}
bool repeatedlyErase(std::string text) {
while (eraseOneInnermostPair(text)) {
}
return text.empty();
}
bool stackScan(const std::string& text) {
if (text.size() % 2 != 0) {
return false;
}
std::vector expectedClosings;
expectedClosings.reserve(text.size() / 2);
for (char current : text) {
if (current == '(') {
expectedClosings.push_back(')');
} else if (current == '[') {
expectedClosings.push_back(']');
} else if (current == '{') {
expectedClosings.push_back('}');
} else {
if (expectedClosings.empty() || expectedClosings.back() != current) {
return false;
}
expectedClosings.pop_back();
}
}
return expectedClosings.empty();
}
public:
bool isValid(std::string s) {
return stackScan(s);
}
};
题解
----
最内层配对
~~~~~~~~~~
一个非空的有效括号串一定包含至少一组最内层括号。最内层括号内部没有其他字符,所以它在当前字符串中必然表现为
相邻的 ``()``、``[]`` 或 ``{}``。
``repeatedlyErase`` 利用这一性质:从左到右寻找一组相邻合法配对,将其删除,然后重新从缩短后的字符串中寻找
下一组。以 ``([]{})`` 为例,字符串可以依次缩短为:
.. code-block:: text
([]{}) -> ({}) -> () -> ""
每次删除的都是已经完整闭合的最内层结构。若原字符串有效,删除后剩余部分仍然有效;不断重复最终一定得到空串。
反过来,若字符串能够通过这些删除变为空串,把删除过程倒序还原时,每一步都只是在已有合法结构中放回一组完整
括号,因此原字符串也有效。
重复扫描
~~~~~~~~
消去法虽然直接对应括号的递归结构,却没有保存上一次扫描获得的信息。每删除两个字符,后续字符都会在
``std::string`` 中发生搬移,下一轮又要从头寻找新的相邻配对。
长度为 ``n`` 的字符串最多删除 ``n / 2`` 组括号。一次查找和删除最坏都需要线性工作,因此总时间最坏达到
``O(n²)``。真正的重复工作不是判断某一对字符,而是反复重建“当前还剩哪些未闭合层级”。
若改为从左向右只扫描一次,就需要在处理每个前缀后保存足够的信息,使下一个字符到来时能够立即判断它是否可以
接在当前前缀之后。
前缀状态
~~~~~~~~
扫描一个前缀后,已经完成闭合的括号不会再影响后面的字符,可以完全丢弃。仍然会影响未来判断的,只有尚未闭合的
左括号。
只保存数量仍然不够。``([)]`` 中三种括号的左右数量最终都相等,但 ``)`` 越过了内层 ``[`` 去关闭外层 ``(``,
所以字符串仍然非法。问题不仅要求知道有哪些左括号未闭合,还必须知道它们应按什么顺序闭合。
假设先读入外层左括号 ``A``,之后又读入内层左括号 ``B``。在 ``B`` 闭合前,任何右括号都不能先关闭 ``A``;
最后出现的未闭合左括号必须最先完成。这正是后进先出的顺序,因此未闭合层级应由栈保存。
期望闭合字符
~~~~~~~~~~~~
栈可以保存左括号本身,读到右括号时再计算它需要匹配哪种类型。``stackScan`` 进一步把这个转换提前完成:
* 读到 ``(`` 时压入将来必须出现的 ``)``;
* 读到 ``[`` 时压入将来必须出现的 ``]``;
* 读到 ``{`` 时压入将来必须出现的 ``}``。
因此 ``expectedClosings`` 从底到顶直接表示当前所有未完成层级的闭合顺序,栈顶就是下一个右括号唯一允许出现的
字符。状态不再保存已经闭合的前缀,也不保存右括号出现前用不到的额外映射关系。
读到右括号时只有三种情况:
* 栈为空:当前右括号左侧没有任何未闭合左括号;
* 栈顶与当前字符不同:当前右括号试图关闭错误类型或越过内层括号;
* 栈顶与当前字符相同:弹出栈顶,表示最近的未闭合层级已经完成。
前两种错误都发生在已经确定的前缀中。后续字符只能追加在右侧,无法回到错误右括号之前补入左括号或改变其类型,
所以可以立即返回 ``false``。
状态推演
~~~~~~~~
以类型交叉的 ``s = "([)]"`` 为例。表中栈按“底部到顶部”书写:
.. list-table::
:header-rows: 1
* - 字符
- 处理前栈
- 动作
- 处理后栈
* - ``(``
- 空
- 压入期望的 ``)``
- ``)``
* - ``[``
- ``)``
- 压入期望的 ``]``
- ``) → ]``
* - ``)``
- ``) → ]``
- 栈顶是 ``]``,类型不匹配
- 立即失败
到第三个字符时,外层 ``(`` 的确等待 ``)``,但它不是最近的未闭合层级。只有先读到 ``]`` 才能关闭内层
``[``。这说明判断不能在全部字符扫描后只比较数量,而必须在每个右括号到来时检查栈顶顺序。
扫描不变量
~~~~~~~~~~
处理完任意前缀后,``expectedClosings`` 恰好保存该前缀中所有未闭合左括号未来需要的右括号,并按实际闭合顺序
排列;栈顶对应最近的未闭合左括号。
读到左括号时,新层级位于所有旧层级内部,把它的期望右括号压入栈顶即可保持不变量。读到匹配的右括号时,栈顶
层级完成并被弹出,其余外层的相对顺序没有变化。任何不匹配右括号都会违反有效括号串的必要闭合顺序,因此立即
拒绝不会遗漏合法答案。
扫描结束后还必须要求栈为空。右括号都匹配成功,只能说明没有多余或错序的右括号;栈非空表示仍有左括号缺少
右侧闭合。奇数长度不可能由完整括号对组成,可以在扫描前直接排除。
代码演进
~~~~~~~~
``repeatedlyErase`` 每轮重新寻找一个已经形成的最内层配对,再通过字符串删除把它从问题中移除。它不保留前一轮
识别出的嵌套层级,所以需要重复扫描和搬移剩余字符。
``stackScan`` 不再修改字符串,而是在第一次遇到左括号时就记录该层级未来需要的闭合字符。相邻配对搜索被一次
顺序扫描替代,字符串删除与字符搬移全部消失;每个右括号只与当前栈顶比较一次。
两种方法对应两层认识:
* 从完整字符串观察时,可以反复消去已经闭合的最内层结构;
* 从前缀增量观察时,只需维护尚未完成的闭合顺序,已经闭合的内容无需保存。
公开入口采用 ``stackScan``。它把消去法反复重建的嵌套关系压缩为一个随扫描增量更新的栈。
复杂度分析
~~~~~~~~~~
.. list-table::
:header-rows: 1
* - 方法
- 时间复杂度
- 工作空间
- 主要代价
* - 反复消去相邻配对
- ``O(n²)``
- ``O(n)``
- 多轮扫描并搬移字符串剩余字符
* - 期望闭合栈
- ``O(n)``
- ``O(n)``
- 每个字符至多入栈或出栈一次
消去法接收字符串副本,副本本身占 ``O(n)`` 空间。栈方法最坏遇到前半段全部为左括号,需要保存
``O(n)`` 个期望右括号。
边界处理
~~~~~~~~
* 奇数长度无法拆成完整括号对,主解法在扫描前返回 ``false``;
* 第一个字符是右括号时,栈为空,立即返回 ``false``;
* 类型数量相同但顺序交叉时,当前右括号与栈顶不匹配,立即返回 ``false``;
* 所有右括号都匹配但扫描结束后栈非空时,说明仍有左括号未闭合;
* 题目保证字符只来自六种括号,因此代码的最后一个分支可以统一处理三种右括号。