[LeetCode 20] [Easy] 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.

Solution

For each character in the string, use a stack to maintain the reverse order of the opening brackets that have been encountered. Append each opening bracket to the end of the stack, if the opening bracket does not exist in the dictionary, then it means that a closing bracket has been encountered, at this stage, if the stack is empty, this means that there is no matching opening bracket left for this closing bracket, you can return False. Else pop the last element in the stack, using that opening bracket as the key, retrieve the matching closing bracket that is required for matching, check if the current closing bracket in the string matches that required bracket, if not return False.

At the end of the loop, check if there are still any remaining items in the stack, the stack should be empty in order to have equal matching opening and closing brackets. If there are still items left in the stack, return False, else return True.

Code

# time: o(n)
# space: o(n)
def isValid(self, s):
    """
    :type s: str
    :rtype: bool
    """
    
    MatchingEndBrackets = {'{': '}', '[': ']', '(': ')' }
    stack = []

    for char in s:
        if char in MatchingEndBrackets:
            stack.append(char)
            continue
        if len(stack) == 0: return False
        bracketToMatch = stack.pop()
        if MatchingEndBrackets[bracketToMatch] != char:
            return False

    return False if len(stack) > 0 else True