NC52 有效括号序列

题目链接：https://www.nowcoder.com/practice/37548e94a270412c8b9fb85643c8ccc2

题目描述

给出一个仅包含字符'(',')','{','}','['和']',的字符串，判断给出的字符串是否是合法的括号序列
括号必须以正确的顺序关闭，"()"和"()[]{}"都是合法的括号序列，但"(]"和"([)]"不合法。

数据范围：字符串长度 0≤n≤10000

要求：空间复杂度 O(n)，时间复杂度 O(n)

示例 1：

输入："()[]{}"
返回值：true

示例 2：

输入："[]"
返回值：true

示例 3：

输入："([)]"
返回值：false

解题代码

import java.util.*;


public class Solution {
    /**
     * 
     * @param s string字符串 
     * @return bool布尔型
     */
    public boolean isValid (String s) {
        // write code here
        //辅助栈
        Stack<Character> stack = new Stack<>();
        //遍历字符串
        for (int i = 0; i < s.length(); i++) {
            //遇到左小括号
            if (s.charAt(i) == '(') {
                //期待遇到右小括号
                stack.push(')');
            } else if (s.charAt(i) == '[') {
                //期待遇到右中括号
                stack.push(']');
            } else if (s.charAt(i) == '{') {
                //期待遇到右打括号
                stack.push('}');
            } else if (stack.isEmpty() || stack.pop() != s.charAt(i)) {
                //必须有左括号的情况下才能遇到右括号
                return false;
            }
        }
        //栈中是否还有元素
        return stack.isEmpty();
    }
}

本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名，转载请...
最后编辑时间为: 2022/07/24 23:16:55