网站导航页设计,手机网站制作套餐,网站制作郑州网站制作,英文案例网站文章目录 1. 题目2. 思路及代码实现#xff08;Python#xff09;2.1 栈 1. 题目
给定一个只包括 (#xff0c;)#xff0c;{#xff0c;}#xff0c;[#xff0c;] 的字符串 s #xff0c;判断字符串是否有效。
有效字符串需满足#xff1a;
左括号必须用相同类型… 文章目录 1. 题目2. 思路及代码实现Python2.1 栈 1. 题目
给定一个只包括 (){}[] 的字符串 s 判断字符串是否有效。
有效字符串需满足
左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。每个右括号都有一个对应的相同类型的左括号。
示例 1
输入s () 输出true
示例 2
输入s ()[]{} 输出true
示例 3
输入s (] 输出false 提示 1 s . l e n g t h 1 0 4 1 s.length 10^4 1s.length104s 仅由括号 ()[]{} 组成
2. 思路及代码实现Python
2.1 栈
判断括号的有效性可以使用「栈」这一数据结构来解决。
我们遍历给定的字符串 s。当我们遇到一个左括号时我们会期望在后续的遍历中有一个相同类型的右括号将其闭合。由于后遇到的左括号要先闭合因此我们可以将这个左括号放入栈顶。
当我们遇到一个右括号时我们需要将一个相同类型的左括号闭合。此时我们可以取出栈顶的左括号并判断它们是否是相同类型的括号。如果不是相同的类型或者栈中并没有左括号那么字符串 s 无效返回 False \text{False} False。为了快速判断括号的类型我们可以使用哈希表存储每一种括号。哈希表的键为右括号值为相同类型的左括号。
在遍历结束后如果栈中没有左括号说明我们将字符串 s 中的所有左括号闭合返回 True \text{True} True否则返回 False \text{False} False。注意到有效字符串只包含括号的长度一定为偶数因此如果字符串的长度为奇数我们可以直接返回 False \text{False} False省去后续的遍历判断过程。
该算法时间复杂度为 O ( n ) O(n) O(n)其中 n n n 是字符串 s s s 的长度算法空间复杂度为存储了的字符串长度大小与存储括号总类的哈希表大小之和。
class Solution:def isValid(self, s: str) - bool:if len(s) % 2 1:return Falsepairs {): (,]: [,}: {,}stack list()for ch in s:if ch in pairs:if not stack or stack[-1] ! pairs[ch]:return Falsestack.pop()else:stack.append(ch)return not stack执行用时44 ms 消耗内存16.44 MB
题解来源力扣官方题解
