Valid Parentheses | Programming Challenges

Problem

Given a string `s` containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid. An input string is valid if: 1) Open brackets are closed by the same type of brackets. 2) Open brackets are closed in the correct order. Example: - Input: s = "()[]{}" - Output: true

Show solution

Solution (TypeScript)

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

  for (const ch of s) {
    if (ch === '(' || ch === '[' || ch === '{') {
      stack.push(ch);
      continue;
    }

    const expected = closingToOpening[ch];
    if (!expected) return false;

    const top = stack.pop();
    if (top !== expected) return false;
  }

  return stack.length === 0;
}

Explanation

Use a stack to track opening brackets. When you see a closing bracket, the top of the stack must be its matching opening bracket. If not, the string is invalid. At the end, the stack must be empty.