678. Valid Parenthesis String

题目链接:678. Valid Parenthesis String

题目

Given a string containing only three types of characters: ‘(‘, ‘)’ and ‘*’, write a function to check whether this string is valid. We define the validity of a string by these rules:

  • Any left parenthesis ‘(‘ must have a corresponding right parenthesis ‘)’.
  • Any right parenthesis ‘)’ must have a corresponding left parenthesis ‘(‘.
  • Left parenthesis ‘(‘ must go before the corresponding right parenthesis ‘)’.
  • ‘*’ could be treated as a single right parenthesis ‘)’ or a single left parenthesis ‘(‘ or an empty string.
  • An empty string is also valid.

  • 原始左右匹配问题基础上,增加了万能匹配符*

递归算法1

每次遇到*的时候,其实有三种可能,左右括号和空。

于是将所有情况递归处理。

这个算法很快就超时了….

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
29
30
31
32
33
34
35
36
class Solution:
def checkValidString(self, s: str) -> bool:
if len(s) == 0 or (len(s) == 1 and s[0] == '*'):
return True
return self.helper(s,[],0)

def helper(self, s, stack, pos):
'''
s:origin string
stack: stack for valid
pos: now index
'''
# 考虑边界条件
if pos == len(s) - 1:
if len(stack) == 1 and stack[0] == '(' and (s[pos]==')' or s[pos]=='*'):
return True
else:
return False

if s[pos] == '*':
# 注意stack传的是指针,不是对象
p1 = self.helper(s[:pos] + '(' + s[pos+1:], stack.copy(), pos)
p2 = self.helper(s[:pos] + ')' + s[pos+1:], stack.copy(), pos)
p3 = self.helper(s[:pos] + ' ' + s[pos+1:], stack.copy(), pos)
return p1 or p2 or p3

if s[pos] == '(':
stack.append('(')
elif s[pos] == ')':
# 空stack遇到右括号
if len(stack) == 0:
return False
# 空stack遇到左括号
else:
stack.pop()
return self.helper(s,stack,pos+1)

递归算法2

参考https://www.cnblogs.com/grandyang/p/7617017.html的递归解法三,将所有匹配转化为数字计算,代码貌似简单了很多,看起来应该不会超时。

实际上比递归算法1超时的还要严重,还是栈比较靠谱。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
def checkValidString(self, s: str) -> bool:
return self.helper(s,0,0)

def helper(self, s, cnt, pos):
'''
s:origin string
cnt: the value of string
pos: now index
'''
for i in range(pos,len(s)):
# 考虑边界条件
if cnt < 0: return False
if s[i] == '(':
cnt += 1
if s[i] == ')':
cnt -= 1
if s[i] == '*':
return self.helper(s,cnt+1,pos+1) or self.helper(s,cnt-1,pos+1) or self.helper(s,cnt,pos+1)
return cnt == 0

两个栈

  • 考虑四种情况*)(*)**(,前两种是确认没问题的结构,第三种考虑)即可,但是最后一种肯定会出问题。
  • 考虑设计两个栈,分别为:左括号栈和星栈。每次遇到右括号时,先使用左括号栈内的元素,左括号栈为空时可以使用星栈,均为空则报错。
  • 如果最终leftstar都有剩余,则挨个匹配,检查是否出现*(的情况。因为不用考虑star的剩余情况,只需要检查left是否为空。
  • 每个栈里边应放入index
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
def checkValidString(self, s: str) -> bool:
left = []
star = []
for i in range(len(s)):
if s[i] == '*':
star.append(i)
elif s[i] == '(':
left.append(i)
elif s[i] == ')':
if len(left):
left.pop()
elif len(star):
star.pop()
else:
return False
while len(left) and len(star):
# *(
if left[-1] > star[-1]:
return False
left.pop()
star.pop()
return len(left) == 0

使用set辅助计算

遍历s中的字符c,利用集合old_set 记录所有当前左括号-右括号的差值

  • c == '(',将 old_set 替换为其所有元素+1

  • c == ')',将 old_set 替换为其所有不小于1的元素 - 1

  • c == '*’,将 old_set 中的所有元素+1,-1后,保留非负元素

遍历结束,判断vset中是否包含0元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
def checkValidString(self, s: str) -> bool:
old_set = set([0])
for c in s:
new_set = set()
if c == '(':
for t in old_set:
new_set.add(t + 1)
elif c == ')':
for t in old_set:
if t > 0:
new_set.add(t - 1)
elif c == '*':
for t in old_set:
new_set.add(t + 1)
new_set.add(t)
if t > 0:
new_set.add(t - 1)
old_set = new_set
return 0 in old_set
  • 如遇左括号,则对set加一
  • 如遇右括号,则对set减一
  • 如果遇到*,则对set 加一、减一、不变
  • 每次减之前,都判断一下是否大于0,以免减为负数。
  • 那这个算法怎么判断的”)(“呢?巧妙的地方就在于,只有set里面大于0的元素才去-1;因此刚开始set只有0元素,所以)不算数。

最后这个算法和递归算法2,其实有相似之处,基本想法都是一致的。

但是实现的方法却不同,时间复杂度降低了很多,很巧妙,参考链接

678. Valid Parenthesis String

https://iii.run/archives/7ef68307890b.html

作者

mmmwhy

发布于

2019-04-22

更新于

2021-05-30

许可协议