2020年10月8号，今天是我写算法的第五天，不知道还能坚持多久，希望一起练习的小朋友能够跟一起加油，一直坚持下去，今天的题目应该是小mi的面试题，希望大家能够跟着我一起学习学习，看看这道的核心内容，来吧，让我们看一眼这题目： 给定一个只包括 ‘(’，’)’，’{’，’}’，’[’，’]’ 的字符串，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。 注意空字符串可被认为是有效字符串。 以上是这道的问题和主要想要执行的需求，本题利用了辅助栈，进行解觉，主要是利用栈的先进后出的原理，在进行入栈操作的时候，如果进入的是左括号（ 的时候，如果下一进栈的是左括号，就继续进栈，如果是右括号），把左括号（出栈操作，则遍历完所有括号后 stack 仍然为空。建立哈希表 dic 构建左右括号对应关系：keykey 左括号，valuevalue 右括号；这样查询 22 个括号是否对应只需 O(1)O(1) 时间复杂度；建立栈 stack，遍历字符串 s 并按照算法流程一一判断。 算法流程
如果 c 是左括号，则入栈 pushpush； 否则通过哈希表判断括号对应关系，若 stack 栈顶出栈括号 stack.pop() 与当前遍历括号 c 不对应，则提前返回 falsefalse。 提前返回 falsefalse
提前返回优点： 在迭代过程中，提前发现不符合的括号并且返回，提升算法效率。 解决边界问题： 栈 stack 为空： 此时 stack.pop() 操作会报错；因此，我们采用一个取巧方法，给 stack 赋初值 ?? ，并在哈希表 dic 中建立 key: ‘?’，value:’?'key: ′ ? ′ ，value: ′ ? ′ 的对应关系予以配合。此时当 stack 为空且 c 为右括号时，可以正常提前返回 falsefalse； 字符串 s 以左括号结尾： 此情况下可以正常遍历完整个 s，但 stack 中遗留未出栈的左括号；因此，最后需返回 len(stack) == 1，以判断是否是有效的括号组合。
class Solution(): def isValid(self,s):#定义函数，输入一个列表类型的数据 dic={'(':')','{':'}','[':']','?':'?'}#定义一个字典也是就是哈希表，方便查找 stack=['?']#把栈进行初始化方便进行遍历 for i in s:#进行循环，寻找列表中的元素 if i in dic:#如在列表中就进入栈 stack.append(i)#进入操作 elif dic[stack.pop()]!=i:#当不能在哈希表匹配返回False return False return len(stack)==1#如果栈的长度是1就说明还是初始的“?”,说明没有元素返回True t=Solution() s=['(',')','{','}'] c=t.isValid(s) print(c)输出结果： D:\python\python.exe C:/Users/ASUS/PycharmProjects/pythonProject1/选择括号.py True
