Valid Parenthesis

题目描述

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

The brackets must close in the correct order, "()"`` and"()[]{}"are all valid but"(]"and"([)]"` are not.

解题方法

当前的character需要更前一个last in的character判断关系的题目，显然是用stack解决

Solution

class Solution(object):
    def isValid(self, s):
        """
        :type s: str
        :rtype: bool
        """
        if not s:
            return True
        stack = []
        for c in s:
            if c in ("(", "[", "{"):
                stack.append(c)
            elif len(stack) == 0:
                return False
            elif c == ")":
                prev = stack.pop()
                if prev != "(":
                    return False
            elif c == "]":
                prev = stack.pop()
                if prev != "[":
                    return False
            elif c == "}":
                prev = stack.pop()
                if prev != "{":
                    return False
        if len(stack) != 0:
            return False

        return True

Reference