Valid Parentheses (LeetCode 20)

20. Valid Parentheses

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

Example 1:
Input: s = "()"
Output: true

Example 2:
Input: s = "()[]{}"
Output: true

Example 3:
Input: s = "(]"
Output: false

import java.util.*;
public class Main {
    public static boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        for (char c : s.toCharArray()) {
            if (c == '(') stack.push(')');
            else if (c == '{') stack.push('}');
            else if (c == '[') stack.push(']');
            else {
                if (stack.isEmpty() || stack.pop() != c) return false;
            }
        }
        return stack.isEmpty();
    }
}

class Solution:
    def isValid(self, s: str) -> bool:
        stack = []
        for c in s:
            if c == '(': stack.append(')')
            elif c == '{': stack.append('}')
            elif c == '[': stack.append(']')
            else:
                if not stack or stack.pop() != c:
                    return False
        return not stack

Type	Value
Time	O(n)
Space	O(n)

• Approach: Push expected closing brackets onto a stack. For each closing bracket, check if it matches the stack top.

• Dry run (s = "()[]{}"):

  • Push ')' for '('
  • Push ']' for '['
  • Push '}' for '{'
  • Match and pop everything → return true