20. Valid Parentheses

发表于 | 分类于

题目描述

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。

有效字符串需满足：

  1. 左括号必须用相同类型的右括号闭合。
  2. 左括号必须以正确的顺序闭合。

注意空字符串可被认为是有效字符串。

示例 1:

输入: "()"
输出: true

示例 2:

输入: "()[]{}"
输出: true

示例 3:

输入: "(]"
输出: false

示例 4:

输入: "([)]"
输出: false

示例 5:

输入: "{[]}"
输出: true

我的解法——栈（AC）

  • 前括号一律入栈，后括号如果跟栈顶符号匹配，栈顶符号出栈如果，若不匹配则返回false
  • 时间复杂度O(n)，空间复杂度O(n)
  • Beat 10%
class Solution(object):
    def isOK(self,a,b):
        if(a == '{' and b == '}'):
            return True
        if(a == '(' and b == ')'):
            return True
        if(a == '[' and b == ']'):
            return True
        return False

    def isValid(self, s):
        """
        :type s: str
        :rtype: bool
        """
        s = list(s)
        stack = []
        
        for i in range(len(s)):
            # 第一个 or 不匹配
            if(len(stack) == 0 or not self.isOK(stack[-1],s[i])):
                stack.append(s[i])
            else:
                stack = stack[:-1]
        
        if(len(stack) == 0):
            return True
        else:
            return False