20. Valid Parentheses

题设

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.

要点

• 栈

想到栈就好做了。栈首遇到对应的字符就弹出。最后栈空表示合法字符。

 public boolean isValid(String s) {
        //明显可以用栈来解决
        if(s.length() == 0 || s == null)
            return false;

        if(s.charAt(0) == ')' || s.charAt(0) == '}' || s.charAt(0) == ']')
            return false;

        Stack<Character> stack = new Stack<Character>();
        for(int i = 0;i < s.length();i++){
            if(s.charAt(i) == '{' || s.charAt(i) == '[' || s.charAt(i) == '('){
                stack.push(s.charAt(i));
                continue;
            }
            if(s.charAt(i) == '}' || s.charAt(i) == ']' || s.charAt(i) == ')'){
                if(stack.empty())
                    return false;

                // stack.peek() 获取栈顶元素
                if(stack.peek() == '(' && s.charAt(i) == ')' || stack.peek() == '{' && s.charAt(i) == '}' ||
                        stack.peek() == '[' && s.charAt(i) == ']') {
                    stack.pop();
                    continue;
                }
                else
                    return false;
            }
        }
        if(stack.empty())
            return true;

        return false;
    }