欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Leecode刷题: 20. 有效的括号

程序员文章站 2022-07-12 12:03:51
...
  1. 有效的括号

题目

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

有效字符串需满足:

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

示例

示例 1:

输入: “()”
输出: true
示例 2:

输入: “()[]{}”
输出: true
示例 3:

输入: “(]”
输出: false
示例 4:

输入: “([)]”
输出: false
示例 5:

输入: “{[]}”
输出: true

解决方案

1

class Solution:
    def isValid(self, s: str) -> bool:
        valid_quotas = [['(',')'],['{','}'],['[',']']]
        if len(s) % 2 != 0: return False
        for i in range(int(len(s)/2)):
            if not [s[i],s[len(s)-i-1]] in valid_quotas:return False
        return True

把输入的字符串从中间一分为二,向左取一个字符,向右取一个字符,看是否可以匹配。
只能解决括号完全对称,成对出现的情况,比如(([[{{}}]])),但无法处理不对称的情况,比如:()()[[{}]]

2

class Solution:
    def isValid(self, s: str) -> bool:
        valid_quotas = ['()','[]','{}']
        for i in valid_quotas:
            while i in s:
                s = s.replace(i,'')
        return (True if len(s) == 0 else False)

如果找到成对的括号,使用replace替换为空字串,这个解决方案的问题在于只能顺序执行小括号、方括号、花括号的替换,顺序有变化,就无法正常识别,比如这种情况,返回的结果就是错误的: ([])

3

对于上面方案的改良,可以解决问题,但花的时间,只能击败2.68%的用户

class Solution:
    def isValid(self, s: str) -> bool:
        while any(('()' in s,'[]' in s, '{}' in s)):
            s = s.replace('()','')
            s = s.replace('[]','')
            s = s.replace('{}','')
        return True if len(s) == 0 else False

执行用时: 112 ms, 在Valid Parentheses的Python3提交中击败了2.68% 的用户
内存消耗: 13.3 MB, 在Valid Parentheses的Python3提交中击败了0.90% 的用户
好惭愧,只击败了2.68%的用户。

4

看了官方题解后,照抄了一下,终于“击败了45.24% 的用户”,问题是让我自己想,我还是想不出来这么精妙的解法啊,是练得不够,还是智商不够:

        # Second try
        stack = []
        mapping = {'}':'{', ')':'(', ']':'['}
        for char in s:
            if char in mapping:
                top_char = stack.pop() if stack else '#'
                if top_char != mapping.get(char):
                    return False
            else:
                stack.append(char)
        return not stack
相关标签: Leecode