首页 > 编程学习 > 【LeetCode】【简单】【2】20. 有效的括号

【LeetCode】【简单】【2】20. 有效的括号

发布时间:2022/11/13 21:27:48

题目:

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

有效字符串需满足:
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。

在这里插入图片描述

最初思路: 考察栈

有三种匹配的情况:
1)“()[]{}”
2)“{[()]}”
3)“{()}[]”
总结规律:
1)s长度为2的倍数
2)第一个都是左括号
3)可以用栈来处理:遇到左括号则入栈,遇到右括号则进行匹配

那么就有代码思路了:

  1. 判断字符串s长度是否为2的倍数,如果不是,返回false;如果是,继续第2步
  2. s进行循环,判断s[0]是否为三个左括号其中一个,如果不是,返回false;如果是,将其加入到list中,继续第3步
  3. 判断s[i]是否为三个左括号其中一个,如果是,将其加入到list中,再循环下一个;如果不是,将其加入到list中,再判断list中最后两个是不是一对,如果是一对,移除最后两个元素,继续循环;如果不是一对,返回false
  4. 最后看list元素是否为空,如果不为空,返回false

代码如下:

class Solution(object):
    def isValid(self,s):
        """
        :type s: str
        :rtype: bool
        """
        left = [str("("),str("["),str("{")]
        right = [str(")"),str("]"),str("}")]
        
        peidui = ["()","{}","[]"]

        valid=True
        stack = [] 
        if (len(s)%2!=0): # 第一步
            valid=False
        else:
            for idx in range(0,len(s)):# 第二步
                if (idx==0):
                    if s[0] not in left:
                        valid=False
                        # print("11111111111111")
                        break
                    else:
                        top = s[idx]
                        stack.append(top)
                else:
                    if s[idx] in left:# 第三步
                        top = s[idx]
                        stack.append(top)
                    else:            
                        top = s[idx]
                        stack.append(top)
                        if(len(stack)<2): # 这里防止list中只有右括号的情况出现
                            # print(stack)
                            valid=False
                            # print("2222222")
                            break
                        else:
                            newp = stack[-2]+stack[-1]
                            # print("newp=",newp)
                            if(newp in peidui):
                                stack = stack[:len(stack)-2]
                                # print("stack=",stack)
                            else:    
                                valid=False
                                # print("33333333333")
                                break      
                if(len(stack)!=0): # 第四步
                    valid=False                
            return valid
t=Solution
print(t.isValid(s="("))

快速解

思路:直接用replace替换"()" “[]” “{}”
代码如下:

class Solution:
    def isValid(self, s):
        while '{}' in s or '()' in s or '[]' in s:
            s = s.replace('{}', '')
            s = s.replace('[]', '')
            s = s.replace('()', '')
        return s == ''

右括号入栈解法

参考:https://leetcode.cn/problems/valid-parentheses/solutions/1737575/by-carlsun-2-ij1t/

class Solution:
    def isValid(self, s: str) -> bool:
        stack = []
        
        for item in s:
            if item == '(':
                stack.append(')')
            elif item == '[':
                stack.append(']')
            elif item == '{':
                stack.append('}')
            elif not stack or stack[-1] != item:# 栈空或者遍历到的元素和栈顶元素不相等
                return False
            else:
                stack.pop()# 遍历到的元素和栈顶元素相等
        
        return True if not stack else False

Copyright © 2010-2022 dgrt.cn 版权所有 |关于我们| 联系方式