[LeetCode Hot 100] LeetCode20. 有效的括号

题目描述

思路：

栈的经典应用。
注意下遇到右括号的代码，即边界情况：

// 遇到右括号,则进行括号匹配
if (!stack.isEmpty() && stack.peek() == match(c)) {
	// 如果匹配则直接弹出栈顶元素
	stack.pop();
} else {
	// 如果不匹配则直接返回false
	return false;
}

方法一：

class Solution {
    public boolean isValid(String s) {
        // 括号匹配问题会使用到栈
        // 在Java中如要要使用栈，建议使用ArrayDeque
        Deque<Character> stack = new ArrayDeque<>();

        for (char c : s.toCharArray()) {
            // 遍历字符串的每一位
            if (c == '(' || c == '{' || c == '[') {
                // 遇到左括号就入栈
                stack.push(c);
            } else {
                // 遇到右括号,则进行括号匹配
                if (!stack.isEmpty() && stack.peek() == match(c)) {
                    // 如果匹配则直接弹出栈顶元素
                    stack.pop();
                } else {
                    // 如果不匹配则直接返回false
                    return false;
                }
            }
        }
        // 如果到最后栈为空,则说明"阔考匹配"
        return stack.isEmpty();
    }

    // 这里额外写一个match函数
    private char match(char c) {
        if (c == ')') return '(';
        if (c == '}') return '{';
        return '[';
    }
}