有效的括号

Posted on Edited on In

题目描述
给定一个只包括 ‘(‘，’)’，’{‘，’}’，’[‘，’]’ 的字符串 s，判断字符串是否有效。有效字符串需满足：

  1. 左括号必须用相同类型的右括号闭合。
  2. 左括号必须以正确的顺序闭合。
  3. 每个右括号都有一个对应的相同类型的左括号。

输入格式
输入共 1 行，包含一个字符串 s。

输出格式
输出共 1 行，如果字符串 s 是有效的括号字符串，输出 “true”；否则输出 “false”。

数据范围
1 ≤ s.length ≤ 10^4
字符串 s 仅由括号 ‘()[]{}’ 组成

输入样例1：

1
()

输出样例1：

1
true

输入样例2：

1
()[]{}

输出样例2：

1
true

输入样例3：

1
(]

输出样例3：

1
false

注意事项

  • 有效的括号问题是栈的经典应用。
  • 遇到左括号时，将其压入栈中；遇到右括号时，检查栈顶元素是否是对应的左括号，如果是，则弹出栈顶元素；否则，返回false。
  • 遍历结束后，如果栈为空，则说明所有括号都正确匹配，返回true；否则，返回false。
  • 需要注意处理空字符串的情况（在本题中，输入字符串长度至少为1，所以不需要特别处理）。

代码实现

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <iostream>
#include <string>
#include <stack>
#include <unordered_map>
using namespace std;

bool isValid(string s)
{
    stack<char> bracketStack;
    unordered_map<char, char> bracketMap = {
        {')', '('},
        {'}', '{'},
        {']', '['}
    };
    
    for (char c : s)
    {
        // 如果是左括号，压入栈中
        if (c == '(' || c == '{' || c == '[')
        {
            bracketStack.push(c);
        }
        // 如果是右括号，检查栈顶元素是否匹配
        else
        {
            // 如果栈为空或者栈顶元素与当前右括号不匹配，返回false
            if (bracketStack.empty() || bracketStack.top() != bracketMap[c])
            {
                return false;
            }
            // 括号匹配，弹出栈顶元素
            bracketStack.pop();
        }
    }
    
    // 如果栈为空，说明所有括号都正确匹配
    return bracketStack.empty();
}

int main()
{
    string s;
    cin >> s;
    
    bool result = isValid(s);
    
    if (result)
    {
        cout << "true" << endl;
    }
    else
    {
        cout << "false" << endl;
    }
    
    return 0;
}

时间复杂度

  • 时间复杂度：O(n)，其中 n 是字符串的长度。我们只需要遍历字符串一次。
  • 空间复杂度：O(n)，最坏情况下，栈的大小可能等于字符串的长度（例如，所有字符都是左括号）。

代码解释

  • 有效的括号问题是栈的经典应用。栈的特点是后进先出（LIFO），这正好符合括号匹配的要求。
  • 我们使用一个哈希表来存储右括号与左括号的对应关系，这样可以快速检查括号是否匹配。
  • 遍历字符串时，对于每个字符：
    • 如果是左括号（’(‘，’{‘，’[‘），则将其压入栈中。
    • 如果是右括号（’)’，’}’，’]’），则检查栈顶元素是否是对应的左括号：
      • 如果栈为空或者栈顶元素与当前右括号不匹配，说明括号无效，返回false。
      • 如果栈顶元素与当前右括号匹配，则弹出栈顶元素，继续遍历。
  • 遍历结束后，如果栈为空，说明所有括号都正确匹配，返回true；否则，说明有左括号没有对应的右括号，返回false。