题目

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

无效字符串需满足：

左括号必须用雷同类型的右括号闭合。
左括号必须以正确的程序闭合。

输出：s = "()"输入：true输出：s = "()[]{}"输入：true输出：s = "(]"输入：false输出：s = "([)]"输入：false输出：s = "{[]}"输入：true

栈

'()[]'和'([])'这两种无效状况，能够看出，只有右括号后面是左括号，它们肯定是一对，能够互相对消的。
利用栈的思维能够很好的解决题目，有种消消乐的感觉。

def isValid(s):  # 如果字符串是奇数，那么必定返回False  if len(s)%2!=0:      return False  hash = {      ')':'(',      ']':'[',      '}':'{'  }  stack = []  for ch in s:      # 如果是右括号      if ch in hash:          # 如果曾经空栈且右括号，间接False          # 如果栈顶的左括号和以后右括号不配对，间接False          if not stack or stack[-1]!=hash[ch]:              return False          # 没空栈，且与栈顶左括号配对，则打消这对括号          stack.pop()      else:          # 如果是左括号，间接入栈          stack.append(ch)  # 通过栈的打消，如果是无效括号，应该是空栈  return not stack

工夫复杂度：O(n)
空间复杂度：O(n+∣∣)，其中 示意字符集，本题中字符串只蕴含6种括号，∣∣=6。栈中的字符数量为 O(n)，而哈希表应用的空间为 O(∣∣)，相加即可失去总空间复杂度。