刷无止境 20 ~ 有效的括号
基本信息
- 题号:20
- 题厂:脸书
- 难度系数:低
给出一组只包含大,中,小括号的字符串,如果括号们能配对就返回 true,否则返回 false
解题思路
- 配对题,常见引用 stack 先进后出原理查询
- 本题为了书写方便,再引入 hashmap 方便查询
class Solution: def isValid(self, s: str) -> bool: # 如果要查询的字符串长度为奇数,则根本不可能配对,提前返回 false if len(s) % 2 == 1: return False # 初始化 stack 和 hashmap stack = [] pairs = { "(": ")", "{": "}", "[": "]" } # 做 for 循环的时候, # 如果遇上前括号,就把对应的后括号放进 stack # 如果遇上后括号,将 stack 最后一个元素取出;如果能配对则 for 循环继续,如果不能配对,提前返回 false ~game over for i in s: if i in pairs: stack.append(pairs[i]) elif not stack: return False else: pop = stack.pop() if pop != i: return False # 做完整个 for 循环都没有返回,如果 stack 为空就返回 true,说明括号们全部配对成功…… return True if not stack else False
Constraints
1 <= s.length <= 104
s
consists of parentheses only'()[]{}'
.
解题前,可以向考官确认除了括号,还会不会有其他符号……
Big O
- Time:O(n)
- Space:引入 stack,故 O(n)
测试
- 配对括号组:‘()’,‘(())’
- 不配对括号组……
总结
一道比较正常的简单题,考察对 stack 的认知水平。引用 stack 后解题方案有好些,但都是大同小异的原理……
stack 常常作为解题关键出现在中难档题里,所以本题需要时常复习,深度理解如何使用 stack 解决问题……