20_Valid Parentheses

[easy] [string, stack]

Given a string containing just the characters'(',')','{','}','['and']', determine if the input string is valid.

The brackets must close in the correct order.

Example:

Input: "(]"
Output: false

Example:

Input: "([)]"
Output: false

Example:

Input: "{[]}"
Output: true

Solution: using stack

The rule is when right parentheses comes, it must be matched with the closest left parentheses on the left with the same type.

So we need to use stack to store all the left parentheses that have not been paired.

def isValid(s):
    """
    :type s: str
    :rtype: bool
    """
    rule = {'(':')', '[':']', '{':'}'}
    stack = []  # store all the unmatched left parentheses
    for item in s:
        # if the item is left parentheses
        if rule.get(item) is not None:
            stack.append(item)
        # if the item is right parentheses, 
        # and on it's left, there has left parentheses
        elif len(stack) > 0 :
            temp = stack.pop()
            if rule.get(temp) != item:
                return False
        # if the item is right parentheses, 
        # and nothing left on the left
        else:
            return False
    return True if len(stack) == 0 else False