内容简介：The more you know the more you know you don't know给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。有效字符串需满足：
The more you know the more you know you don't know
题目描述
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。
示例 1:
输入: "()"
输出: true
示例 2:
输入: "()[]{}"
输出: true
示例 3:
输入: "(]"
输出: false
示例 4:
输入: "([)]"
输出: false
示例 5:
输入: "{[]}"
输出: true
解题
思路
-
发现字符串为空时，直接返回true
-
判断字符串的长度。如果为奇数则直接返回false
-
将括号的对应关系存入字典中
-
定义一个列表模拟栈数据结构，当字符为右括号时入栈，当字符串为左括号时候出栈
-
判断两字符时候相同
代码
class Solution:
def isValid(self, s: str) -> bool:
# 是否为空
if not s:
return True
# 是否为奇数
if len(s) % 2 != 0:
return False
# 初始化列表，模拟出栈、入栈
tmp_list = []
# 定义括号对应关系
valid_dict = {
")": "(",
"]": "[",
"}": "{"
}
# 遍历字符串
for i in s:
# 如果是左括号则入栈，append到列表的末尾
if i in ["(", "[", "{"]:
tmp_list.append(i)
continue
# 如果右括号则和列表的末尾对比
if i in [")", "]", "}"]:
# 若栈为空，则返回错误
if not tmp_list:
return False
# 若相同，则从队列中删除末尾的元素
if tmp_list[-1] == valid_dict[i]:
tmp_list.pop()
continue
# 若存在其他字符，直接返回错误
else:
return False
# 返回判断栈是否为空，若空，则返回true，反正返回false
return not tmp_list
复杂度分析
时间复杂度：O(n)，因为我们一次只遍历给定的字符串长度
空间复杂度：O(n)，最糟糕的情况是所有的字符串都为左括号，此时所有的字符都需要保存到列表中
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持 码农网
本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。
个性化网页设计与鉴赏
梁景红 / 西安电子科技大学出版社 / 2003-07-14 / 22.00
本书比较全面地介绍了网页设计应注意的相关问题， 在网页设计基础方面着重讲解了网页框架、页面元素、色彩设计，分析了一些人们容易忽视的细小环节，如页面装饰物、图片、文字、连接等。书中结合实例分析了优秀网页的设计创意思想，可以给读者提供一些启示。书中还介绍了作为网页设计者需要了解的信息管理和技术应用，以及网站VI设计和视觉美学等必要知识，读者可针对各种类别的站点具体实践这些知识，寻找进行网页设计的切入点......一起来看看 《个性化网页设计与鉴赏》 这本书的介绍吧!
