20. Valid Parentheses

Question

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.
3. Every close bracket has a corresponding open bracket of the same type.

Example 2

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

Solution 1: Hash + Stack

class Solution:
    def isValid(self, s: str) -> bool:
        dic = {
            '(' : ')',
            '{' : '}',
            '[' : ']'
        }
        
        stack = []
        for i in s:
            if i in dic:
                stack.append(i)
            else:
                if not stack:
                    return False
                
                top = stack.pop()
                if dic[top] != i:
                    return False
        return not stack

Time Complexity: O(N)
Space Complexity: O(N)

Solution 2: Stack

class Solution:
    def isValid(self, s: str) -> bool:
        stack = []
        for i in s:
            if i == '(':
                stack.append(')')
            elif i == '{':
                stack.append('}')
            elif i == '[':
                stack.append(']')
            elif (not stack) or (stack.pop() != i):
                return False
        return not stack

Time Complexity: O(N)
Space Complexity: O(N)

Reference

https://leetcode.com/problems/valid-parentheses/discuss/9178/Short-java-solution

Follow-up: Check if a Parentheses String Can Be Valid

TODO

Time Complexity: O()
Space Complexity: O()