#20 Valid Parentheses

Problem Statement

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

Intuition

A stack naturally models the nesting structure of brackets. Every time we see an opening bracket, we push it. When we see a closing bracket, we check if it matches the top of the stack.

Approach

1. Create an empty stack.
2. For each character in the string:
   • If it's an opening bracket, push it onto the stack.
   • If it's a closing bracket, check if the stack is non-empty and the top matches. If not, return false.
3. Return true if the stack is empty at the end.

Solution

function isValid(s: string): boolean {
  const stack: string[] = [];
  const pairs: Record<string, string> = {
    ")": "(",
    "]": "[",
    "}": "{",
  };

  for (const ch of s) {
    if (ch in pairs) {
      if (stack.pop() !== pairs[ch]) return false;
    } else {
      stack.push(ch);
    }
  }

  return stack.length === 0;
}

Complexity Analysis