leetcode - 6.有效的括号

有效的括号

题目

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

有效字符串需满足:
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。

解法一

思路

后遇到的左括号总是先匹配右括号,先遇到的左括号总是后匹配右括号,符合栈先进后出的原理。

dic = {')': '(','}': '{',']': '['}
遍历字符串s,如果i是左括号加到栈顶,
如果i是右括号,判断d里面有没有,如果有我们要出栈,但是这里可能会有栈空的情况要注意判断,那出栈就出错了,
所以如果在dic里面,栈不是空的,且栈顶的元素与i相等,
如果不满足这两个条件直接返回False
如果满足就出栈,最后栈应该是空的

解法

class Solution:
	def isValid(self, s: str) -> bool:
		if len(s) % 2 == 1:
			return False
		dic = {')': '(','}': '{',']': '['}
		stack = []
		for i in s:
			# 如果i是右括号
			if i in dic:
				if not stack or dic[i] != stack[-1]:
					return False
				stack.pop()
			# 如果i是左括号
			else:
				stack.append(i)
		return not stack

时间复杂度:O(n)

执行用时:32 ms

内存消耗:15.1 MB

解法二

思路

dic = {'{': '}',  '[': ']', '(': ')', '?': '?'}
上面提到了空栈出栈的问题,索性这里直接定义一个长度为一的栈stack = ['?']
遍历字符串s,如果i是左括号也就是在dic里面,入栈
如果i是右括号,dic[出栈的元素]不等于i,直接返回False
最后stack的长度还是1,说明进栈的元素全都出栈了,s是有效的括号

解法

class Solution:
	def isValid(self, s: str) -> bool:
		if len(s) % 2 == 1:
			return False
		dic = {'{': '}',  '[': ']', '(': ')', '?': '?'}
		stack = ['?']
		for i in s:
			# 如果i是左括号
			if i in dic:stack.append(i)
			# 如果i是右括号
			elif dic[stack.pop()] != i:return False
		return len(stack) == 1

时间复杂度:O(n)

执行用时:32 ms

内存消耗:15 MB

上一篇:多线程爬虫之生产者和消费者模式


下一篇:字典详细操作