博客

LeetCode 热题 HOT 100 —— 20. 有效的括号（python解法）

题目介绍：

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

有效字符串需满足：

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

测试样例

示例 1：

输入：s = "()"
输出：true

示例 2：

输入：s = "()[]{}"
输出：true

示例 3：

输入：s = "(]"
输出：false

示例 4：

输入：s = "([)]"
输出：false

示例 5：

输入：s = "{[]}"
输出：true

解题思路：

参考栈先进后出的原则即可

1. 首先定义一个列表

stack = []
dic = {']':'[',")":'(',"}":'{'}
sc = [']','}',')']

2. 然后开始循环遍历整个字符串，每次遍历的时候首先判断下当前栈是否为空，如果为空且不等于任何右括号则直接返回False，如果为空且为左括号，则进栈。

for item in range(len(s)):
    if stack == [] and s[item] in sc:
        return False
    if stack == [] or s[item] not in dic.keys():
        stack.append(s[item])

3. 在遍历的时候，如果栈内不为空，则需要判断，则需要判断当前元素与栈顶元素是否匹配，由于上面已经做过判断，左括号会直接进栈，所以当前元素都是右括号，判断当前右括号对应的左括号和栈顶元素是否相等即可，如果相等就栈顶元素出栈，当前元素不入栈，如果不匹配则当前元素进栈。

if dic[s[item]] == stack[-1]:
      stack.pop()
  else:
      stack.append(s[item])

4. 当所有元素遍历完成，判断栈是否为空，如果为空则符合有效括号，如果不为空则不符合。

if stack ==[]:
    return True
else:
    return False

完整代码

class Solution:
    def isValid(self, s: str) -> bool:
        stack = []
        dic = {']':'[',")":'(',"}":'{'}
        sc = [']','}',')']
        for item in range(len(s)):
            if stack == [] and s[item] in sc:
                return False
            if stack == [] or s[item] not in dic.keys():
                stack.append(s[item])
            else:
                if dic[s[item]] == stack[-1]:
                    stack.pop()
                else:
                    stack.append(s[item])
        if stack ==[]:
            return True
        else:
            return False

写法未考虑空间复杂度，占用内存较高。