LeetCode-20. Valid Parentheses

[ninehills]

问题

https://leetcode.com/problems/valid-parentheses/tabs/description

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.

思路

使用stack的思想，碰到({[就压栈，碰到)}]就出栈，出栈时栈空或者遍历结束后栈不为空，则not valid

解答

class Solution(object):
    def isValid(self, s):
        """
        :type s: str
        :rtype: bool
        """
        stack = []
        m = {'[': ']', '{': '}', '(': ')'}
        for c in s:
            if c in m:
                stack.append(c)
            else:
                if not stack:
                    return False
                else:
                    k = stack.pop()
                    if c == m[k]:
                        continue
                    else:
                        return False
        if not stack:
            return True
        else:
            return False


print Solution().isValid("[[[{{{{(((((())))))}}}}]]]")
print Solution().isValid("[{}[{{{{({{}}((((({{}}))))))}}}}]]]")

[ninehills]

#4 20170729