Headstone lamp - leetcode grind (62)

20. Valid Parentheses

Posted on Oct 26, 2023
# O(n) time || O(n) space
def is_valid(self, s: str) -> bool:
    closed_to_open = {'}': '{', ']': '[', ')': '('}
    stack = []
    for br in s:
        if br in closed_to_open:
            if not stack or stack.pop() != closed_to_open[br]:
                return False
        else:
            stack.append(br)

    return not stack
  1. Initialize an empty stack.
  2. Traverse the string character by character.
  3. For each character:
    • If it’s an open bracket (’(’, ‘{’, or ‘[’), push it onto the stack.
    • If it’s a closing bracket, check the top of the stack:
      • If the stack is empty, the string is not valid.
      • If the top of the stack is not the corresponding open bracket, the string is not valid.
      • If the top of the stack is the corresponding open bracket, pop the stack.
  4. After traversing the string, if the stack is not empty, the string is not valid.
  5. If we pass the above checks, the string is valid.