20. Valid Parentheses

Given a string s 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.

Example 1:

Input: s = "()"
Output: true

Example 2:

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

Example 3:

Input: s = "(]"
Output: false

Example 4:

Input: s = "([)]"
Output: false

Example 5:

Input: s = "{[]}"
Output: true

Constraints:

1 <= s.length <= 10⁴
s consists of parentheses only '()[]{}'.

Source

Code

In [1]:

def valid_parentheses(s):
    '''
    Time Complexity O(n)
    Space Complexity O(n)
    '''
    stack = []
    for char in s:
        if char in {'(', '[', '{'}:  # make sure to use Hash table to store
            stack.append(char)  # this has a O(1) access
        if char in {')', ']', '}'}:
            if len(bstack) == 0 or (stack.pop() + char) not in {'()', '[]', '{}'}:
                return False
    return stack == []

In [2]:

def valid_parentheses(s):
    '''
    Time Complexity O(n)
    Space Complexity O(n)
    '''
    stack = []
    mapping = {'}': '{', ')': '(', ']': '['}
    for char in s:
        if char not in mapping:
            stack.append(char)
        else:
            top_element = stack.pop() if stack else '#'
            if mapping[char] != top_element:
                return False
    return not stack

Check

In [3]:

s = "()"
valid_parentheses(s)

Out[3]:

True

In [4]:

s = "(]"
valid_parentheses(s)

Out[4]:

False

In [5]:

s = "([)]"
valid_parentheses(s)

Out[5]:

False

In [6]:

s = "{[]}"
valid_parentheses(s)

Out[6]:

True

In [7]:

s = "()[]{}"
valid_parentheses(s)

Out[7]:

True

In [8]:

s = "([)]"
valid_parentheses(s)

Out[8]:

False

In [9]:

s = "{[]}"
valid_parentheses(s)

Out[9]:

True

In [10]:

s = '('
valid_parentheses(s)

Out[10]:

False

In [11]:

s = ')'
valid_parentheses(s)

Out[11]:

False

In [12]:

s = ''
valid_parentheses(s)

Out[12]:

True