# 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

```java
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 == '}');
    }
}
```

```java
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();
    }
}
```