动态更新bing图片

力扣索引

020 有效地括号 Easy

原始问题

Given a string s containing just the characters ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[‘ and ‘]’, determine if the input string is valid.
An input string is valid if:

  1. Open brackets must be closed by the same type of brackets.
  2. Open brackets must be closed in the correct order.

给定一个只包括 ‘(‘，’)’，’{‘，’}’，’[‘，’]’ 的字符串 s ，判断字符串是否有效。有效字符串需满足：1.左括号必须用相同类型的右括号闭合。2.左括号必须以正确的顺序闭合。
Input：s = “()”
Output：true
Input：s = “(]”
Output：false
Constraints：

  • 1 <= s.length <= 104
  • s consists of parentheses only ‘()[]{}’.

    条件反射-栈

    题读完，大部分人的第一想法就是使用栈，字符串过一遍就解决了。下面的代码是使用栈解决问题的基本逻辑，这份代码有注释，直接copy了。下面有原文链接， ```python class Solution(object): def isValid(self, s):
    1.   d = {'}': '{', ']': '[', ')': '('} #字典①
    2.   e = {'{':'}','[':']','(':')'} #字典②
    3.   if len(s) % 2 != 0: #判断长度不是二的倍数 返回False
    4.       return False
    5.   if s[-1] in e:  # 判断字符串末尾是字典②中的key值则返回False（不用d.values,那样会增加执行时间）
    6.       return False
    7.   lst=[]   # 新建列表用于放字符串的左括号（当遇到左括号的右括号时，删除列表的左括号）
    8.   for i in s:  # 循环字符串
    9.       if i in e: # 字符在字典②的key值中则为True（不用d.values，节省执行时间）
    10.           lst.append(i)  #在列表中添加左括号
    11.       elif lst and i in d: # 当lst元素不为空，循环的字符在d的key值时执行缩进块
    12.           if lst[-1]==d[i]: # 当列表末尾元素 等于 字典①中的value值时(列表最后一位元素的右括号)
    13.               lst.pop() #删除列表中末尾的左括号
    14.           else:
    15.               return False
    16.       else:
    17.           return False
    18.   return not lst

    来源https://leetcode.cn/problems/valid-parentheses/solution/python-by-6evdkxu4j1-v1og/

  1. --not lst。  当lst为空时，返回True，非空时返回False<br />--时间复杂度O(n), n=len(s)<br />       [图解过程](https://leetcode.cn/problems/valid-parentheses/solution/zhu-bu-fen-xi-tu-jie-zhan-zhan-shi-zui-biao-zhun-d/)，<br />原理相同，但简介一些的代码：
  2. ```python
  3. class Solution:
  4.     def isValid(self, s: str) -> bool:
  5.         dic = {')':'(',']':'[','}':'{'}
  6.         stack = []
  7.         for i in s:
  8.             if stack and i in dic:
  9.                 if stack[-1] == dic[i]: stack.pop()
  10.                 else: return False
  11.             else: stack.append(i)
  12.         return not stack
  13. #链接：https://leetcode.cn/problems/valid-parentheses/solution/zhu-bu-fen-xi-tu-jie-zhan-zhan-shi-zui-biao-zhun-d/

换个思路-字符串匹配

但是仔细想想这个题，没有那么难啊。为什么？ 因为是字符串问题，只需要最中间的满足配对就可以了啊。

  1. class Solution:
  2.     def isValid(self, s: str) -> bool:
  3.         if len(s) % 2 != 0:
  4.             return False
  5.         while '()' in s or '[]' in s or '{}' in s:
  6.             s=s.replace("{}",'')
  7.             s=s.replace('[]','')
  8.             s=s.replace("()",'')
  9.         return s==""

image.png

-20220530，忙于论文好久没刷力扣了，以后要抽时间每天来一道。