20. Valid Parentheses

Problem

Given a string containing just the characters ‘(’, ‘)’, ‘{’, ‘}’, ‘[’ and ‘]’, determine if the input string is valid.

An input string is valid if:

  • Open brackets must be closed by the same type of brackets.
  • Open brackets must be closed in the correct order.

Note that an empty string is also considered valid.

Example 1:

Input: "()"
Output: true

Example 2:

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

Example 3:

Input: "(]"
Output: false

Thought Process

  • split the parenthesis into two types:
    • lefts = “{”, “[“, “(”
    • rights = “}”, “]”, “)”
  • for the current char,
    • if char in lefts, push char into the stack
    • if char in rights, compare char with the stack top
      • if char = “}” and top ! “{”
      • if char = “]” and top ! “[”
      • if char = “)” and top ! “(”
    • return false
  • loop thru stack (this step is important, make sure now stack is empty), then return true

White Board

Below is the white board:

Code

class Solution:
    def isValid(self, s):
        st = []
        lefts = ["(", "{", "["]
        match = {
            ")":"(",
            "}":"{",
            "]":"["
        }

        if len(s) == 0:
            return True
        if len(s) == 1:
            return False


        for c in s:
            if c in lefts:
                st.append(c)
            else:
                if len(st) == 0:
                # if stack is empty
                    return False
                if st.pop() != match[c]:
                    return False
        #important, need to check st is empty
        if len(st) == 0:
            return True
        else:
            return False

def test():
    s ="(("
    va = Solution().isValid(s)
    print(va)

test()
False

Complexity

  • Time complexity is O(n*m)
  • used additional ds to creat stack

Optimization

Will try to figure out a recursive solution in the future.