LeetCode | 20. Valid Parentheses

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.

About Stack

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

Image

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