Leetcode 20: Valid Parentheses

leetcode_20.md

Description

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 must be closed by the same type of brackets.
2. Open brackets must be closed in the correct order.

Link to the original problem

Example 1

Input: s = "()"
Output: true

Example 1

Input: s = "()[]{}"
Output: true

Example 1

Input: s = "(]"
Output: false

Constraints:

• 1 <= s.length <= 104
• s consists of parentheses only '()[]{}'.

Idea

1. So the goal is to find out if a string s is valid. OK, so what makes a string "valid"?
2. The description already explained it: a) open brackets are closed by same type of brackets, and b) open brackets are closed in right order.
3. So, a) is quite straight forward. For example, a '(' has to be closed by a ')' and a '{' has to be closed by a '}'. For b), it is a bit abstract actually. Let's just see some examples. Apparently we can tell, "([])" is in right order, but "([)]". What's the difference?
4. The difference is for "([)]", we expect the ']' to close '[' first, then ')' closes '('.
5. To generalize, it's basically saying we should "close the rightmost non-closed open brackets X before closing any non-closed open brackets before X". Not sure if this makes it easier to visualize (I hope so, lol).
6. OK, we get the idea now. So how do we solve the problem?
7. Naturally, I would go search the string s from left to right and check a) if it's an open bracket, record it somewhere and move on, b) if it's a closed bracket, check if it matches the "rightmost" open bracket X. If they match, we can "forget" about this pair of brackets, because they "kinda" cancel each other. And the next time we meet a new closed bracket, we only care about the open bracket (if there's one) before X. If they don't match, easy, it's invalid.
8. So which data structure can support this operation nicely? Stack, right?
9. Stack works in a "first in last out" / "last in first out" manner, which means, we can always store the open brackets on the top of the stack, and when we meet a closed bracket, we check if it matches whatever stays on the top of the stack. If they match, we can easily "cancel" them by popping out of the open bracket on top of the stack. And if they don't match, we know the string is invalid.
10. One more thing I want to mention is that, a valid string will definitely cancel all the pairs. So, at the end, the stack should be empty, if not, we know it's not valid.
11. The code should explain itself now.
12. Btw, see more similar questions in the references. The logic are almost the same, see if you can solve them easily.
13. Thanks for reading!

Solution

Javascript

const isValid = function(s) {
  const leftParens = ["(", "{", "["];
  const map = { ")": "(", "}": "{", "]": "[" };
  const stk = [];
  for (const ch of s) {
    if (leftParens.includes(ch)) {
      stk.push(ch);
    } else {
      if (!stk.length) return false;
      if (stk[stk.length - 1] !== map[ch]) return false;
      stk.pop();
    }
  }
  return stk.length == 0;
};

References

1. Leetcode 726: Number of Atoms
2. Leetcode 1544: Make the String Great
3. Leetcode 1047: Remove All Adjacent Duplicates In String