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.

Reprint policy

《20-Valid-Parentheses》 by Isaac Zhou is licensed under a Creative Commons Attribution 4.0 International License
Previous
Python Decorator
What is a Python DecoratorEssentially, Python Decorator is a type of Python function.A Python decorator enables addition
2020-03-15
Next
1-TwoSum
Problem Given an array of integers, return indices of the two numbers such that they add up to a specific target. You ma
2020-03-14
TOC