Problem: 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.

Thinking:

Assumption: {[()]}() is valid.

Since there are only brackets in the string, we can easily make assumption that if the length of the string is not an even number, there must be a lonely parenthesis that is not valid.

Look at the pattern, if we have one opening bracket, then if it is valid, there must be a closing bracket. And if it is valid, the closing bracket is gonna be checked after everything is checked in this corresponding bracket. Therefore it is a FIFO behavior, because we’re always checking the closest correspondence. Therefore using a stack to check which one is nearest is ideal. At the end, we just need to check if there is anything left in the stack.

```
public class Solution {
public boolean isValid(String s) {
if (s == null || s.length() ==0) return true;
if (s.length() % 2 != 0) return false;
Stack stack = new Stack();
Map map = new HashMap();
map.put('(', ')');
map.put('{', '}');
map.put('[', ']');
for (int i = 0; i < s.length(); i++) {
char current = s.charAt(i);
Character correspondence = map.get(current);
if (!stack.empty() && current == stack.peek()) {
stack.pop();
} else if (correspondence != null) {
stack.push(correspondence);
} else {
return false;
}
}
return stack.empty();
}
}
```