内容简介：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)，最糟糕的情况是所有的字符串都为左括号，此时所有的字符都需要保存到列表中
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持 码农网
猜你喜欢:
本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。
算法Ⅰ~Ⅳ(C++实现):基础、数据结构、排序和搜索
Sedgewick / 高等教育出版社 / 2002-1 / 49.00元
本书通过C++实现方案以简洁、直接的方式对书中的算法和数据结构进行表述，并向学生提供在实际应用中验证这种方法的手段。 本书广泛地论述了与排序、搜索及相关应用有关的基本数据结构和算法。覆盖了数组、链表、串、树和其他基本数据结构，更多地强调抽象数据类型(ADT)、模块化程序设计、面向对象程序设计和C++类。本书包括排序、选择、优先队列ADT实现和符号表ADT(搜索)实现，配有帮助学生学习计算......一起来看看 《算法Ⅰ~Ⅳ(C++实现):基础、数据结构、排序和搜索》 这本书的介绍吧!
