LC 20. Valid Parentheses

The problem

Solution

My first thought was to use regex lookaheads to solve this. However, given the topic was stack, I went in that direction. I tried writing out all the cases in a long if-else block, but it felt messy, so I collapsed that into a Map of the bracket pairs. In fact, this is similar to what I did on Roman to Integer.

Though it took some time, I realized that closing brackets would fail if the previous entry was not the corresponding closing bracket. By handling this, I accounted for a failing test case, ([)], where the brackets aren't paired correctly. I could push any opening brackets, and if I encountered a closing where the previous bracket wasn't the correct opening, I immediately return false. Lastly, the final return checks if the stack is empty to handle cases where any opening brackets are left unclosed.

function isValid(s: string): boolean {
  if (s.length % 2 !== 0) {
    return false
  }

  let stack = []
  let bracketMap = { '(': ')', '[': ']', '{': '}' }
  for (let bracket of s) {
    // Push all opening brackets
    if (bracketMap[bracket]) {
      stack.push(bracket)
    } else {
      // Remove pair if current is a closing bracket of previous
      if (bracket === bracketMap[stack[stack.length - 1]]) {
        stack.pop()
      } else {
        return false
      }
    }
  }

  return stack.length === 0
}