Valid Parentheses 423

Question

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

Example

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

Solution

用stack实现。遍历string中所有字符，遇到前括号就压入栈中，遇到后括号就看栈顶元素（与该后括号距离最近的前括号）是否和该后括号配对，配对则返回true，不配对或此时stack为空则返回false。

代码如下：

public class Solution {
    public boolean isValidParentheses(String s) {
        Stack<Character> stack = new Stack<Character>();
        for (Character c : s.toCharArray()) {
        if ("({[".contains(String.valueOf(c))) {
                stack.push(c);
            } else {
               if (!stack.isEmpty() && is_valid(stack.peek(), c)) {
                   stack.pop();
               } else {
                   return false;
               }
           }
       }
       return stack.isEmpty();
    }

    private boolean is_valid(char c1, char c2) {
        return (c1 == '(' && c2 == ')') || (c1 == '{' && c2 == '}')
            || (c1 == '[' && c2 == ']');
    }
}