0020. Valid Parentheses

题目信息

题号:
  1. 有效的括号

难度:

Easy

主题:

字符串、栈、括号匹配

原题:

LeetCode 0020

重点:

从反复消去最内层配对,推导到用栈直接维护尚未完成的闭合顺序

题目重述

给定一个只包含 (、)、[、]、{、} 的字符串 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)

多轮扫描并搬移字符串剩余字符

期望闭合栈

O(n)

O(n)

每个字符至多入栈或出栈一次

消去法接收字符串副本,副本本身占 O(n) 空间。栈方法最坏遇到前半段全部为左括号,需要保存 O(n) 个期望右括号。

边界处理

  • 奇数长度无法拆成完整括号对,主解法在扫描前返回 false;

  • 第一个字符是右括号时,栈为空,立即返回 false;

  • 类型数量相同但顺序交叉时,当前右括号与栈顶不匹配,立即返回 false;

  • 所有右括号都匹配但扫描结束后栈非空时,说明仍有左括号未闭合;

  • 题目保证字符只来自六种括号,因此代码的最后一个分支可以统一处理三种右括号。