有效的括号字符串

有效的括号字符串

题目说明

给定一个只包含三种字符的字符串: (, )*,写一个函数来检验这个字符串是否为有效字符串。有效字符串具有如下规则:

  1. 任何左括号(必须有相应的右括号)
  2. 任何右括号)必须有相应的左括号(
  3. 左括号(必须在对应的右括号之前)
  4. 可以被视为单个右括号),或单个左括号(,或一个空字符串。
  5. 一个空字符串也被视为有效字符串。

示例 1:

1
2
输入: "()"
输出: True

示例 2:

1
2
输入: "(*)"
输出: True

示例 3:

1
2
输入: "(*))"
输出: True

注意:

1
1. 字符串大小将在 [1,100] 范围内。

解决方案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution:
def checkValidString(self, s: str) -> bool:
stack = list()
stars = list()
index = 0
while index < len(s):
tmp = s[index]
if tmp == '(':
stack.append({tmp: index})
elif tmp == '*':
stars.append({tmp: index})
else:
if len(stack) > 0:
stack.pop()
else:
if len(stars) > 0:
stars.pop()
else:
return False
index += 1

while len(stack) > 0 and len(stars) > 0:
if (stack[len(stack) - 1]['('] > stars[len(stars) - 1]['*']):
return False
stack.pop()
stars.pop()

return len(stack) == 0

说明: 如果您有更好的解决方案或者本人写的有什么问题,请多多指教!