Problem Description

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.

Solution

Based on the property of FILO, stack can help with match the brackets. I only push the left half of bracket and when it comes to a right part of bracket, I use it to match the top of stack, if success, pop the element, if fail, return false.

Code

class Solution {
public boolean isValid(String s) {
Stack stack = new Stack();
char[] stringArr = s.toCharArray();
int len = s.length();
int i = 0;
String temp;
for (i = 0; i < len; i++) {
try {
if (stringArr[i] == ‘(‘ || stringArr[i] == ‘[‘ || stringArr[i] == ‘{‘) {
stack.push(stringArr[i]);
} else if (‘(‘ == stack.peek() && stringArr[i] == ‘)’ || ‘[‘ == stack.peek() && stringArr[i] == ‘]’ || ‘{‘ == stack.peek() && stringArr[i] == ‘}’) {
stack.pop();
} else {
return false;
}
} catch (Exception e) {
return false;
}
}
return stack.empty();

}

Better Solution

When it comes to the left half of bracket, push its right part into a stack.
When it comes to the right half of bracket, match it with the top of stack(pop it if match).
At last check the emptiness of stack

Code

public boolean isValid(String s) {
Stack stack = new Stack();
for (char c : s.toCharArray()) {
if (c == ‘(‘)
stack.push(‘)’);
else if (c == ‘{‘)
stack.push(‘}’);
else if (c == ‘[‘)
stack.push(‘]’);
else if (stack.isEmpty() || stack.pop() != c)
return false;
}
return stack.isEmpty();
}