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``; * 所有右括号都匹配但扫描结束后栈非空时,说明仍有左括号未闭合; * 题目保证字符只来自六种括号,因此代码的最后一个分支可以统一处理三种右括号。