로고조성현

0020 Valid Parentheses

Solved at: 2022-07-10

Question

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.

Solution

This is a classic stack problem.

I missed some details:

  • Remember pop() doesn't take any argument.
  • Remember to check the final condition. When the list is not empty at the end, then return False.
class Solution:
    def isValid(self, s: str) -> bool:
        stack = []
        opening = ["(", "{", "["]
        closing = [")", "}", "]"]

        for _, c in enumerate(s):
            if c in opening:
                stack.append(c)
                continue
            if not stack:
                return False
            e = stack.pop()
            if opening.index(e) != closing.index(c):
                return False
        if not stack:
            return True
        return False

Results

Runtime

  • 67 ms, faster than 11.18% of Python3 online submissions for Valid Parentheses.

Memory Usage

  • 13.9 MB, less than 24.23% of Python3 online submissions for Valid Parentheses.

Other Answers Online

  • All of the other solutions I found had similar approaches.
  • This is funny.
public boolean isValid(String s) {
  while (s.indexOf("{}") != -1 || s.indexOf("[]") != -1 ||
         s.indexOf("()") != -1) {
    s = s.replace("()", "");
    s = s.replace("[]", "");
    s = s.replace("{}", "");
  }
  return s.isEmpty();
}