题目

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

有效字符串需满足：

  1. 左括号必须用相同类型的右括号闭合。
  2. 左括号必须以正确的顺序闭合。
  3. 注意空字符串可被认为是有效字符串。

image.png

思路

遇到右括号，只要判断离右括号最近的是不是相应的最括号即可。利用栈结构，去寻找右括号距离最近的左括号。

  1. class Solution:
  2.     def isValid(self, s: str) -> bool:
  3.         bracket_map = {'(':')', '{':'}', '[':']'}
  4.         left_bracket_stack = []
  5.         for ch in s:
  6.             if ch in bracket_map:
  7.                 left_bracket_stack.append(ch)
  8.             else:
  9.                 # 判断栈顶是不是相应的左括号
  10.                 if left_bracket_stack and bracket_map[left_bracket_stack.pop()] == ch:
  11.                     continue
  12.                 else:
  13.                     return False
  14.         return left_bracket_stack == []