LeetCode-020 有效的括号

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

有效字符串需满足：

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/valid-parentheses

解题思路

遍历字符串, 遇到左括号入栈, 右括号则弹出栈顶并比较
如果比较发现不能组成一对正确的括号, 返回false
遍历完字符串后, 检查栈是否为空, 如果是有效的括号则遍历完后栈必定为空

代码

class Solution {
    public boolean isValid(String s) {
        char[] letters = s.toCharArray();
        LinkedList<Character> stack = new LinkedList<>();
        for (char letter : letters) {
            // 如果是左括号, 入栈
            if (letter == '{' || letter == '[' || letter == '(') {
                stack.push(letter);
                // 如果是右括号, 弹出栈顶并比较
            } else if (letter == '}' || letter == ']' || letter == ')') {
                // 弹出栈顶
                Character top = stack.pollFirst();
                if (top == null || letter == '}' && top != '{' || letter == ']' && top != '[' || letter == ')' && top != '(') {
                    return false;
                }
            }
        }
        // 如果括号匹配正确, 则stack为空, 只要有左括号未弹出, 则说明括号匹配不正确
        return stack.isEmpty();
    }
}