LeetCode #20 Valid Parentheses

Posted on | Post modified | In , , , , , , , ,

Problem

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

Examples

1
2
Input: "()"
Output: true
1
2
Input: "()[]{}"
Output: true
1
2
Input: "(]"
Output: false
1
2
Input: "([)]"
Output: false
1
2
Input: "{[]}"
Output: true

Solution

Method:

Time Complexity: O(n)

Space Complexity: O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def isValid(self, s):
        """
        :type s: str
        :rtype: bool
        """
        lookup = {')': '(', ']': '[', '}': '{'}
        stack = []
        
        for char in s:
            if char in lookup.keys():
                if not stack:
                    return False
                else:
                    if stack.pop() != lookup[char]:
                        return False
            else:
                stack.append(char)
        
        return not stack

or

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution(object):
    def isValid(self, s):
        """
        :type s: str
        :rtype: bool
        """
        if len(s) % 2 != 0:
            return False
        
        opening = set('([{')
        matches = set([('(', ')'), ('[', ']'), ('{', '}')])
        stack = []
        
        for paren in s:
            if paren in opening:
                stack.append(paren)
            else:
                if not stack:
                    return False
                last_open = stack.pop()
                if (last_open, paren) not in  matches:
                    return False

        return not stack