Valid Parentheses

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

An input string is valid if:

1. Open brackets must be closed by the same type of brackets.

2. Open brackets must be closed in the correct order.

Note that an empty string is also considered valid.

Example 1:

Input:
 "()"

Output:
 true

Example 2:

Input:
 "()[]{}"

Output:
 true

Example 3:

Input:
 "(]"

Output:
 false

Example 4:

Input:
 "([)]"

Output:
 false

Example 5:

Input:
 "{[]}"

Output:
 true

Analysis

这种先入后出的特性很适合用栈Stack，因此利用一个stack来记录之每个字符，遍历每个字符，如果下一个字符是可以closed栈顶字符的同类括号，则出栈；最终结果就是检测这个栈是否为空

Solution

class Solution {
    public boolean isValid(String s) {
        if (s == null) {
            return false;
        }
        Stack < Character > stack = new Stack < Character > ();
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            if (!stack.isEmpty() && match(stack.peek(), ch)) {
                stack.pop();
            } else {
                stack.push(ch);
            }
        }
        return stack.isEmpty();
    }
    boolean match(char ch1, char ch2) {
        return (ch1 == '(' && ch2 == ')') ||
            (ch1 == '[' && ch2 == ']') ||
            (ch1 == '{' && ch2 == '}');
    }
}

class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        for(char c : s.toCharArray()){
            switch(c){
                case ']': if(stack.isEmpty() || stack.pop()!='[') return false; break;
                case ')': if(stack.isEmpty() || stack.pop()!='(') return false; break;
                case '}': if(stack.isEmpty() || stack.pop()!='{') return false; break;
                default: stack.push(c);
            }
        }
        return stack.isEmpty();
    }
}