Leetcode-20-Valid Parentheses

Valid Parentheses

leetcode: https://leetcode.com/problems/valid-parentheses/

Description:

Given a string s 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.

Analysis:

Situation1: there are extra brackets in the left

Situation2: no extra brackets but the type of brackets inside isn’t matched

Situation3: there are extra brackets in the right

Idea:

**solution **

Step1: traverse the brackets and we only record the half of rackets into stack, and when they match the corresponding brackets in the string, then pop the element

Step2: Stack is FILO, so the top element is the corresponding bracket of the cloest element

Step3: there are 3 situations

Situation1: If the whole string has been traversed, but the stack isn’t empty, it means there are extra left brackets.

Situation2: when traverse is doing, but the stack is empty, it means there are extra right brackets.

Situation3: when traverse is doing, but the element in the stack can’t match element of the string, return false;

Code:

class Solution {
    public boolean isValid(String s) {
        //set the stack to record the corresponding brackets
        Stack <Character> result = new Stack<>();
        //traverse the string to get each bracket
        for (int i=0; i<s.length(); i++){
            //record the corresponding brackets
            if(s.charAt(i) == '('){
                result.push(')');
            }
            else if(s.charAt(i) == '['){
                result.push(']');
            }
            else if(s.charAt(i) == '{'){
                result.push('}');
            }
            //Stack is FILO, so the top element is the corresponding bracket of the cloest element
            //if the element is not the left part of the bracket, then compare the current element with top element of stack.
            else if(result.isEmpty() || result.peek() != s.charAt(i)){
                return false;
            }
            // if match remove the corresponding racket in the stack
            else{
                result.pop();
            }
        }
        //verify the stack is empty or not, if it's not empty it means there are extra brackets exists.
        return result.isEmpty();
    }
}