20. Valid Parentheses

#stack

Problem

Valid Parentheses - LeetCodeLeetCode

Intuition

Time Complexity

Space Complexity

Solution

class Solution {
    public boolean isValid(String s) {
        // n -> s.length()
        // Time Complexity: O(n), traversing through the string 
        // Space Complexity: O(n), storing the characters of string in stack
        Stack<Character> stack = new Stack<>();

        for(char ch: s.toCharArray()) {
            if(ch == '{') {
                stack.push('}');
            } else if(ch == '(') {
                stack.push(')');
            } else if(ch == '[') {
                stack.push(']');
            } else if(stack.isEmpty() || stack.pop() != ch) {
                // If the stack is empty or the top element of the stack does not match the current character,
                // it means the current character does not have a corresponding opening bracket,
                // or it does not match the expected closing bracket for the previous opening bracket.
                // In either case, the string is not valid.
                return false;
            }
        }
        
        // After processing all the characters, if the stack is empty,
        // it means all opening brackets have been matched with their corresponding closing brackets,
        // and there are no remaining unmatched brackets in the stack.
        // Otherwise, if the stack is not empty, there are unmatched opening brackets in the string.
        return stack.isEmpty();
    }
}