Valid Parentheses

20. Valid Parentheses

分析

利用栈来检查括号匹配：

核心规则：
- 左括号 (, [, { 是合法起始符号，直接入栈
- 遇到右括号 ), ], } 时，检查栈顶的左括号是否能匹配：
  - 如果匹配，则栈顶元素出栈
  - 如果不匹配，字符串无效，直接返回 false
- 遍历结束后，如果栈为空，则字符串有效；否则无效。
匹配判断：
- 两个字符匹配的条件是：abs(栈顶字符 - 当前字符) <= 2
  - ASCII 值中：
    - ( 和 ) 相差 1
    - [ 和 ] 相差 2
    - { 和 } 相差 2

C++代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32


class Solution
{
public:
    bool isValid(string s)
    {
        // 特殊情况处理：空字符串
        if (s.empty())
            return true;

        // 使用栈存储左括号
        std::stack<char> stk;

        // 遍历字符串
        for (char c : s)
        {
            // 如果是左括号，入栈
            if (c == '(' || c == '[' || c == '{')
                stk.push(c);
            else
            {
                // 如果栈不为空并且栈顶括号能匹配当前右括号
                if (stk.size() && abs(stk.top() - c) <= 2)
                    stk.pop();  // 匹配成功，栈顶出栈
                else
                    return false;  // 不匹配，直接返回 false
            }
        }

        // 遍历结束后检查栈是否为空
        return stk.empty();
    }
};