# Valid Parentheses

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();

}
}
``````
Advertisements