Valid Parentheses 括号开闭

Easy, Dynamic Programming

Question

给定string只含 '(', ')', '{', '}', '[', ']'，判断string是否valid

Example: "()[]{}": true
"([)]" : false

Solution

论坛一个coder的方法，做减法，把配对的括号一一去除。想法非常简单，缺点是complexity会比较高。

class Solution(object):
    def isValid(self, s):
        """
        :type s: str
        :rtype: bool
        """
        if len(s) % 2 != 0:
            return False
        while "()" in s or "[]" in s or "{}" in s:
            s = s.replace("()","").replace("[]","").replace("{}","")
        return s == ''

更加有效的方法是利用堆栈。

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