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