Python实现-LeetCode（0020）-有效的括号（简单

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
有效字符串需满足：
  1、左括号必须用相同类型的右括号闭合。
  2、左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。

示例 1:

输入: "()"
输出: true

示例 2:

输入: "()[]{}"
输出: true

示例 3:

输入: "(]"
输出: false

示例 4:

输入: "([)]"
输出: false

示例 5:

输入: "{[]}"
输出: true

题解思路1（正则法-re.findall()）：
LeetCode中提交执行结果-执行用时：200 ms，内存消耗：13.5 MB。

import re
class Solution:
    def isValid(self, s: str) -> bool:
        no_space_s = s.replace(' ','')
        while no_space_s:
            re_list = re.findall('\(\)|\[]|{}',no_space_s)
            if not re_list:
                return False
            for char in re_list:
                no_space_s = no_space_s.replace(char,'')
        return True

print('字符串“()”是否有效：',Solution().isValid("()"))
print('字符串“”是否有效：',Solution().isValid(""))
print('字符串“[”是否有效：',Solution().isValid("["))
print('字符串“]”是否有效：',Solution().isValid("]"))
print('字符串“{[]}”是否有效：',Solution().isValid("{[]}"))
print('字符串“()[]{}”是否有效：',Solution().isValid("()[]{}"))
print('字符串“(]”是否有效：',Solution().isValid("(]"))
print('字符串“([)]”是否有效：',Solution().isValid("([)]"))

运行结果：

字符串“()”是否有效： True
字符串“”是否有效： True
字符串“[”是否有效： False
字符串“]”是否有效： False
字符串“{[]}”是否有效： True
字符串“()[]{}”是否有效： True
字符串“(]”是否有效： False
字符串“([)]”是否有效： False

题解思路2（正则法-re.search()）：
LeetCode中提交执行结果-执行用时：312 ms，内存消耗：13.5 MB。

import re
class Solution:
    def isValid(self, s: str) -> bool:
        no_space_s = s.replace(' ','')
        while no_space_s:
            if re.search('\(\)|\[]|{}',no_space_s):
                re_string = re.search('\(\)|\[]|{}',no_space_s).group()
                no_space_s = no_space_s.replace(re_string, '')
            else:
                return False
        return True

print('字符串“()”是否有效：',Solution().isValid("()"))
print('字符串“”是否有效：',Solution().isValid(""))
print('字符串“[”是否有效：',Solution().isValid("["))
print('字符串“]”是否有效：',Solution().isValid("]"))
print('字符串“{[]}”是否有效：',Solution().isValid("{[]}"))
print('字符串“()[]{}”是否有效：',Solution().isValid("()[]{}"))
print('字符串“(]”是否有效：',Solution().isValid("(]"))
print('字符串“([)]”是否有效：',Solution().isValid("([)]"))

运行结果：

字符串“()”是否有效： True
字符串“”是否有效： True
字符串“[”是否有效： False
字符串“]”是否有效： False
字符串“{[]}”是否有效： True
字符串“()[]{}”是否有效： True
字符串“(]”是否有效： False
字符串“([)]”是否有效： False

题解思路3（堆栈法）：
LeetCode中提交执行结果-执行用时：32 ms，内存消耗：13.5 MB。

class Solution:
    def isValid(self, s: str) -> bool:
        dic = {'{': '}',  '[': ']', '(': ')', '#': '#'}
        stack = ['#']
        for c in s:
            if c in dic:
                stack.append(c)
            elif dic[stack.pop()] != c: return False
        return len(stack) == 0

print('字符串“()”是否有效：',Solution().isValid("()"))
print('字符串“”是否有效：',Solution().isValid(""))
print('字符串“[”是否有效：',Solution().isValid("["))
print('字符串“]”是否有效：',Solution().isValid("]"))
print('字符串“{[]}”是否有效：',Solution().isValid("{[]}"))
print('字符串“()[]{}”是否有效：',Solution().isValid("()[]{}"))
print('字符串“(]”是否有效：',Solution().isValid("(]"))
print('字符串“([)]”是否有效：',Solution().isValid("([)]"))

运行结果：

字符串“()”是否有效： True
字符串“”是否有效： True
字符串“[”是否有效： False
字符串“]”是否有效： False
字符串“{[]}”是否有效： True
字符串“()[]{}”是否有效： True
字符串“(]”是否有效： False
字符串“([)]”是否有效： False

题解思路4（堆栈法）：
LeetCode中提交执行结果-执行用时：56 ms，内存消耗：13.3 MB。

class Solution:
    def isValid(self, s: str) -> bool:
        dic = {'}': '{',  ']': '[', ')': '('}
        stack = []
        for char in s:
            if char in dic:
                top_element = stack.pop() if stack else '#'
                if dic[char] != top_element:
                    return False
            else:
                stack.append(char)
        return not stack

print('字符串“()”是否有效：',Solution().isValid("()"))
print('字符串“”是否有效：',Solution().isValid(""))
print('字符串“[”是否有效：',Solution().isValid("["))
print('字符串“]”是否有效：',Solution().isValid("]"))
print('字符串“{[]}”是否有效：',Solution().isValid("{[]}"))
print('字符串“()[]{}”是否有效：',Solution().isValid("()[]{}"))
print('字符串“(]”是否有效：',Solution().isValid("(]"))
print('字符串“([)]”是否有效：',Solution().isValid("([)]"))

运行结果：

字符串“()”是否有效： True
字符串“”是否有效： True
字符串“[”是否有效： False
字符串“]”是否有效： False
字符串“{[]}”是否有效： True
字符串“()[]{}”是否有效： True
字符串“(]”是否有效： False
字符串“([)]”是否有效： False