Leecode刷题： 20. 有效的括号

20. 有效的括号

题目

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

有效字符串需满足：

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

示例

示例 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