5、有效的括号-Python-LeetCode-20
程序员文章站
2023-12-27 07:58:15
题目给定一个只包括 ‘(’,’)’,’{’,’}’,’[’,’]’ 的字符串,判断字符串是否有效。有效字符串需满足:左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。注意空字符串可被认为是有效字符串。示例 1:输入: "()"输出: true示例 2:输入: "()[]{}"输出: true示例 3:输入: "(]"输出: false示例 4:输入: "([)]"输出: false示例 5:输入: "{[]}"输出: true解法这题有想到碰...
题目
给定一个只包括 ‘(’,’)’,’{’,’}’,’[’,’]’ 的字符串,判断字符串是否有效。
有效字符串需满足:
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。
示例 1:
输入: "()"
输出: true
示例 2:
输入: "()[]{}"
输出: true
示例 3:
输入: "(]"
输出: false
示例 4:
输入: "([)]"
输出: false
示例 5:
输入: "{[]}"
输出: true
解法
这题有想到碰到闭括号,判断上一个开括号是不是配对的,但一开始没想到用栈(后进先出的特点),废了点时间;现在讲下用到栈后的主要思路,配对的话用字典就行了:
(1)碰到开括号,就将它放入栈中,稍后再处理
(2)碰到闭括号,就推出并判断栈顶的元素,如果栈顶无元素或者栈顶的开括号与闭括号不匹配,则表达式无效
(3)判断完所有元素后,如果栈为空,则元素全部匹配,表达式有效,反之无效
代码如下:
class Solution(object):
def isValid(self, s):
stack = []
map = {'(': ')', '{': '}', '[': ']'}
for item in s:
if item in map:
stack.append(item)
else:
if item in map.values():
if stack:
tmp = stack.pop()
else:
return False
if map[tmp] != item:
return False
return not stack
该算法主要和s的长度有关,其余栈的操作时间复杂度为O(1),一层循环所以时间复杂度为O(n)
奥利给!
本文地址:https://blog.csdn.net/weixin_43927540/article/details/107359971