0020. Valid Parenthesis #

题目 #

给定一个只包括 '('， ')'，'{'，'}'，'['，']' 的字符串 s，判断字符串是否有效。
有效字符串需满足:
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
- 每个右括号都有一个对应的相同类型的左括号。

思路 #

栈 #

可使用栈求解括号匹配问题
逢左括号入栈，逢右括号出栈
逢右括号 不匹配 / 遇栈空，或遍历结束时栈非空，则括号失配

代码 #

栈 #

class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        
        for (int i=0; i<s.length(); i++) {
            /** 逢左括号入栈 */
            char bracket = s.charAt(i);
            if (bracket == '{' || bracket == '(' || bracket == '[') {
                stack.push(bracket);
                continue;
            }
            
            /** 逢右括号出栈并检查匹配情况 */
            if (stack.empty() == true) reutrn false;
            char topElement = stack.pop();
            if (bracket == ')' && topElement != '(') return false;
            if (bracket == '}' && topElement != '{') return false;
            if (bracket == ']' && topElement != '[') return false;
        }
        
        return stack.empty() == true;
    }
}