[LeetCode] 20. Valid Parentheses

</br>

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.

</br>

Solution

We should know that if the string is valid parentheses, the string has to have pairing characters and should close in the correct order.

In this way, the most inner brackets and the first close bracket in the entire string should contain no other brackets. And this can be our way in.

By applying stack, we can push any open parentheses onto stack, and when we encounter the first close parentheses, it has to match the character that pops out the stack, otherwise this string is no valid parentheses.

Additionally, the code is using stack.peek() function to find out the current value of the stack without removing it.

The code is shown as below.

Java

public class Solution {
    public boolean isValid(String s) {
        
        Stack<Character> stack = new Stack<Character>();
        
        for(int i = 0; i<s.length(); i++) {
            
            if(s.charAt(i) == '(' || s.charAt(i) == '[' || s.charAt(i) == '{')
                stack.push(s.charAt(i));
            else if(s.charAt(i) == ')' && !stack.empty() && stack.peek() == '(')
                stack.pop();
            else if(s.charAt(i) == ']' && !stack.empty() && stack.peek() == '[')
                stack.pop();
            else if(s.charAt(i) == '}' && !stack.empty() && stack.peek() == '{')
                stack.pop();
            else
                return false;
        }
        
        return stack.empty();
    }
}

</br>