侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 471 篇文章
  • 累计创建 108 个标签
  • 累计收到 9 条评论

目 录CONTENT

文章目录

【栈】有效的括号

GabrielxD
2022-09-14 / 0 评论 / 0 点赞 / 20 阅读 / 402 字 / 正在检测是否收录...

题目

20. 有效的括号


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

有效字符串需满足:

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

示例 1:

输入:s = "()"
输出:true

示例 2:

输入:s = "()[]{}"
输出:true

示例 3:

输入:s = "(]"
输出:false

提示:

  • 1 <= s.length <= 10^4
  • s 仅由括号 '()[]{}' 组成

解题

方法一:栈模拟

思路

遍历字符串:

  • 遇到左括号就把同类型的右括号入栈。
  • 遇到右括号时,如果栈为空或者该括号与栈顶元素不同,那么该括号一定没有匹配项,返回 false

遍历完成后如果栈不为空就说明有没匹配上的左括号,返回 false,否则所有括号都是有效的,返回 true

代码

class Solution {
    public boolean isValid(String s) {
        Deque<Character> stack = new LinkedList<>();
        for (char ch : s.toCharArray()) {
            switch (ch) {
                case '(':
                    stack.push(')');
                    break;
                case '[':
                    stack.push(']');
                    break;
                case '{':
                    stack.push('}');
                    break;
                default:
                    if (stack.isEmpty() || ch != stack.pop()) return false;
            }
        }
        return stack.isEmpty();
    }
}
class Solution {
public:
    bool isValid(string s) {
        if (s.length() & 1) return false;
        stack<char> stk;
        for (char& ch : s) {
            switch (ch) {
                case '(':
                    stk.push(')');
                    break;
                case '[':
                    stk.push(']');
                    break;
                case '{':
                    stk.push('}');
                    break;
                default:
                    if (stk.empty() || ch != stk.top()) return false;
                    else stk.pop();
            }
        }
        return stk.empty();
    }
};
0

评论区