Parentheses - 20. Valid Parentheses

20. 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

思路：

使用栈来做，遇到左括号入栈，遇到右括号出栈，如果不匹配就不合法。

代码：

java：

class Solution {

    /*public boolean isValid(String s) {

        if (s == null || s.length() == 0) return true;
        Stack<Character> stack = new Stack<>();
        
        for (Character ch : s.toCharArray()) {
            if (ch == '(') {
                stack.push(')');
            } else if ( ch == '[') {
                stack.push(']');
            } else if ( ch == '{') {
                stack.push('}');
            } else {
                if (stack.isEmpty() || stack.pop() != ch) return false;
            }
        }
        
        return stack.isEmpty();
    }*/
    
    public boolean isValid(String s) {
        if (s == null || s.length() == 0) return true;
        
        // use char[] as stack api
        char[] stack = new char[s.length()];
        int top = 0;
        
        for (char ch : s.toCharArray()) {
            if (ch == '(' || ch == '{' || ch == '[') {
                stack[top++] = ch;
            } else if (ch == ')' && top > 0 && stack[top-1] == '(') {
                top--;
            } else if (ch == '}' && top > 0 && stack[top-1] == '{') {
                top--;
            } else if (ch == ']' && top > 0 && stack[top-1] == '[') {
                top--;
            } else {
                return false;
            }
        }
        
        return top == 0; // 栈为空
    }
}