Leetcode 20.有效的括号

发表于 | 更新于 | 分类于

题目描述

给定一个只包括 ‘(‘，’)’，’{‘，’}’，’[‘，’]’ 的字符串，判断字符串是否有效。

有效字符串需满足：

1
2
3
1. 左括号必须用相同类型的右括号闭合。
2. 左括号必须以正确的顺序闭合。
3. 注意空字符串可被认为是有效字符串。

示例 1:

1
2
输入: "()"
输出: true

示例 2:

1
2
输入: "()[]{}"
输出: true

示例 3:

1
2
输入: "(]"
输出: false

示例 4:

1
2
输入: "([)]"
输出: false

示例 5:

1
2
输入: "{[]}"
输出: true

题目分析

使用栈来读取每个括号, 如果栈顶的括号与将压入的括号相对, 则弹出栈顶元素, 否则入栈.

最后检查是否栈为空, 如非空则为非法字符串.

源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    bool isValid(string s) {
        if(s.size()%2 != 0) return false;
        // 如果字符串字符数目为奇数则一定有单个的括号
        stack<char>* st = new stack<char>(); // 新建指针以便结束时删除
        st->push('1');
        for(int i=0; i<s.size(); ++i) {
            if(st->top() == s[i]-1 || st->top() == s[i]-2) {
                st->pop();
            }else {
                st->push(s[i]);
            }
        }
        bool a = st->top() == '1';
        delete st;
        return a;
    }
};
0%