Problem 20: Valid Parentheses

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:

1 2	Input: "()" Output: true

Example 2:

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

Example 3:

1 2	Input: "(]" Output: false

Example 4:

1 2	Input: "([)]" Output: false

Example 5:

1 2	Input: "{[]}" Output: true

Good solution for efficiency

class Solution:
    def isValid(self, s):
        """
        :type s: str
        :rtype: bool
        """
        stack = []
        left = ['(','{','[']
        right = [')','}',']']
        mapping = dict(zip(right,left))
        for i in range(len(s)):
            if s[i] in mapping:
                if not stack or mapping[s[i]] != stack.pop():
                    return False
            else:
                stack.append(s[i])
        return not stack

left and right are lists. mapping is a dictionary, which combines right and left using dict and zip function. Searching/matching in dictionary would be more efficient than in list.

Pythonic way to express checking:

if s[i] in mapping:
    if not stack or mapping[s[i]] != stack.pop():
    	return False
else:
	stack.append(s[i])

If s[i] is not ‘)’,’}’,’]’, then stack.append(s[i]); if s[i] is ‘)’,’}’,’]’, then compare it with stack.pop() — the top element in stack. Concise code speeds the execution…

My ugly solution

class Solution:
    def isValid(self, s):
        """
        :type s: str
        :rtype: bool
        """
        
        dict1 = {'(':1, '{':2, '[':3}
        dict2 = {')':'(', '}':'{', ']':'['}
        stack = []

        for n in range(len(s)):
            char = s[n]
            if char in dict1:
                stack.append(char)
            elif char in dict2:
                if stack == []:
                    return False
                if dict2[char] == stack[-1]:
                    stack.pop()
                else:
                    return False
            else:
                return False
        return stack == []

Too many “if” checks slow the solution.

1 2	if stack == []: return False

This check above for test case without left brackets:

“]”

if dict2[char] == stack[-1]:
	stack.pop()
else:
	return False

This check above for test case in disorder:

“(])”