给定一个只包括 ‘(‘，‘)‘，‘{‘，‘}‘，‘[‘，‘]‘ 的字符串，判断字符串是否有效。
有效字符串需满足：
注意空字符串可被认为是有效字符串。
示例 1:
输入: "()" 输出: true
示例 2:
输入: "()[]{}"
输出: true
示例 3:
输入: "(]" 输出: false
示例 4:
输入: "([)]" 输出: false
示例 5:
输入: "{[]}"
输出: true
Python3:
class Solution:
def isValid(self, s):
"""
:type s: str
:rtype: bool
"""
leng = len(s)
print(leng)
if not leng:
return True
elif leng % 2 == 0:
count = {
‘{‘: [],
‘}‘: [],
‘[‘: [],
‘]‘: [],
‘(‘: [],
‘)‘: []
}
maping = {‘}‘: ‘{‘, ‘]‘: ‘[‘, ‘)‘: ‘(‘}
circle = []
for index, char in enumerate(s):
count[char].append(index)
if len(count[‘{‘]) < len(count[‘}‘]) or len(count[‘[‘]) < len(count[‘]‘]) or len(count[‘(‘]) < len(
count[‘)‘]):
return False
if char in [‘]‘, ‘}‘, ‘)‘]:
left_index = count[maping[char]][-1]
circle.append([left_index, index])
count[maping[char]].pop(-1)
count[char].pop(0)
lenth_circle = len(circle)
for i in range(lenth_circle - 1):
for j in range(i + 1, lenth_circle):
if (circle[i][0] < circle[j][0] < circle[i][1] < circle[j][1]) or (
circle[j][0] < circle[i][0] < circle[j][1] < circle[i][1]):
return False
if len(count[‘{‘]) != len(count[‘}‘]) or len(count[‘[‘]) != len(count[‘]‘]) or len(count[‘(‘]) != len(
count[‘)‘]):
return False
return True
else:
return False
当时想想好复杂啊，结果以提交报错执行时间太长，回头想想是我忽略了一些东西。由于限定条件内层一定是[ ]、{ }、 ( )，所以用栈原理就可以解决
Python3:
class Solution:
def isValid(self, s):
"""
:type s: str
:rtype: bool
"""
if not s:
return True
else:
tmp_list = []
mapping = {‘}‘: ‘{‘, ‘]‘: ‘[‘, ‘)‘: ‘(‘}
left_list = mapping.values()
for char in s:
if char in left_list:
tmp_list.insert(0, char)
else:
if not tmp_list or tmp_list[0] != mapping[char]:
return False
else:
tmp_list.pop(0)
if tmp_list:
return False
return True
基于python列表的实际实现可以稍微提升一下性能
Python3:
class Solution:
def isValid(self, s):
"""
:type s: str
:rtype: bool
"""
if not s:
return True
else:
tmp_list = []
mapping = {‘}‘: ‘{‘, ‘]‘: ‘[‘, ‘)‘: ‘(‘}
left_list = mapping.values()
for char in s:
if char in left_list:
tmp_list.append(char)
else:
if not tmp_list or tmp_list[-1] != mapping[char]:
return False
else:
tmp_list.pop(-1)
if tmp_list:
return False
return True
领扣简单版--有效的括号（Valid Parentheses）
原文：https://www.cnblogs.com/explore-the-world/p/9618487.html