有效的括号序列

题目

给定一个字符串所表示的括号序列,包含以下字符: '(', ')', '{', '}', '[' and ']', 判定是否是有效的括号序列。

样例
括号必须依照 "()" 顺序表示, "()[]{}" 是有效的括号,但 "([)]"则是无效的括号。

分析

很简单的一道题目,用栈进行匹配即可。

代码


public class Solution {
    /**
     * @param s: A string
     * @return: whether the string is a valid parentheses
     */
    public boolean isValidParentheses(String s) {
        
        if (s == null || s.length() < 1 ) return true;
        
        // 匹配必然为偶数
        if(s.length() % 2 != 0) return false;
        
        ArrayDeque stack = new ArrayDeque<>();

        for(int i = 0; i < s.length(); i++ ) {
            switch(s.charAt(i)) {
                case '[':
                case '(':
                case '{':
                    stack.push(s.charAt(i));
                    break;
                default:
                    if (stack.size() < 1) return false;
                    char c = stack.pop().charValue();
                    if(
                        c == '[' && s.charAt(i) == ']'
                        || c == '(' && s.charAt(i) == ')'
                        || c == '{' && s.charAt(i) == '}'
                    ){
                        continue;
                    } else {
                        return false;
                    }
            }
        }
        
        return stack.size() == 0;
    }
}
Show Comments

Get the latest posts delivered right to your inbox.