## Description

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.

## Solution

This is a classical problem called "Parenthesis Matching". Generally, we use Stack to solve the problem.

### Thought

We push each character of the string given into a stack from left to right in order.

String : "{[(){}]}"
Stack : '{' ← ' [' ← '(' ...

When the character is a right parenthesis no matter what kind it is( ')', ']' or '}' ), we pop the peek character of the stack to see whether they are matched.

String : "{[(){}]}"
The next character : ')'
Stack : '{' ' [' → '('

If so, we continue to push the next character, if not, the problem ends and return false.

String : "{[(){}]}"
Stack : '{' ← '[' ← '{'

If all the characters of the string have been pushed successfully, the stack must be checked if it's empty.

String : "{[(){}]}" -- Stack : Empty -- Return true
String : "{[(){}]}((" -- Stack : '(' '(' -- Return false

The problem will return true if the stack is empty finally.

## Code ``````class Solution {
public boolean isValid(String s) {
int len = s.length();
boolean result = false;
Stack <Character> check = new Stack<Character>();
for(int i = 0;i<len;i++){
if(s.charAt(i)=='('){
check.push('(');
}
else if(s.charAt(i)=='['){
check.push('[');
}
else if(s.charAt(i)=='{'){
check.push('{');
}
else if(s.charAt(i)==')'){
if(!check.isEmpty() && check.pop()=='('){
continue;
}
else{
return result;
}
}
else if(s.charAt(i)==']'){
if(!check.isEmpty() && check.pop()=='['){
continue;
}
else{
return result;
}
}
else if(s.charAt(i)=='}'){
if(!check.isEmpty() && check.pop()=='{'){
continue;
}
else{
return result;
}
}
}
if(check.isEmpty()){
result = !result;
}
return result;
}
}``````
Comments Write a Comment
• The algorithm looks awesome.