TS LeetCode 20: Valid Parentheses - (Easy)

Problem

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

An input string is valid if:

Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.
Every close bracket has a corresponding open bracket of the same type.

Code

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

  for (const char of s) {
    if (char === '(' || char === '[' || char === '{') {
      stack.push(char);
    } else {
      const top = stack.pop();
      if (top !== pair[char]) {
        return false;
      }
    }
  }

  return stack.length === 0;
}

Approach

We need to check that all brackets in the string are opened and closed in the correct order and by the correct type.

The natural data structure for this is a stack, because the last opened bracket must be the first one to close (LIFO).

1. Create an empty stack to store opening brackets.

2. Create a mapping of closing → opening brackets for quick lookup.

3. Traverse the string:

   • If the character is an opening bracket, push it onto the stack.
   • If it's a closing bracket, pop the top from the stack and check if it matches.
   • If it doesn’t match or the stack is empty, the string is invalid.

4. After the loop, the string is valid only if the stack is empty.