0020 Valid Parentheses

Solved at: 2022-07-10

Question

• Valid Parentheses - LeetCode

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();
}