LeetCode - 20. Valid Parentheses

Thoughts:

There are two types of valid parentheses.

1. ()[] (parallel pairs)

2. [()] (nested pairs)

But they share a same feature…

If I pick up an open bracket,

the next one need to be another open bracket

or the same type closed bracket.

And if I keep picking up open brackets,

I need a data structure to store them,

until I pick up a closed bracket.

Then I need to pop and check the latest one, is it coupled with the current closed bracket or not.

In this situation, I think stack is a good option.

The time complexity will be O(n) because of the iteration.

Thoughts visuzlization:

s = "()[]"
map = {
  ')': '(',
  ']': '[',
  '}': '{',
}
stack = []

"()[]" stack = ['(']
 i
it's open bracket, just push to stack

"()[]" stack = []
  i
it's closed bracket,
pop '('
then check map[')'] and '(' are same, means they are a couple

"()[]" stack = ['[']
   i
it's open bracket, just push to stack

"()[]" stack = []
    i
it's closed bracket,
pop '['
then check map[']'] and '[' are same, means they are a couple

Code:

/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function (s) {
  const stack = [];
  const map = {
    ')': '(',
    ']': '[',
    '}': '{',
  };
  for (let char of s) {
    if (char === '(' || char === '[' || char === '{') {
      stack.push(char);
    } else {
      const top = stack.pop();
      if (top !== map[char]) return false;
    }
  }
  return stack.length === 0;
};

Reference

Original link

stack data structure intro