题目
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
每次遇到*
的时候,其实有三种可能,左右括号和空。
于是将所有情况递归处理。
这个算法很快就超时了....
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超时的还要严重,还是栈比较靠谱。
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
两个栈
- 考虑四种情况
*)
、(*
、)*
、*(
,前两种是确认没问题的结构,第三种考虑)
即可,但是最后一种肯定会出问题。 - 考虑设计两个栈,分别为:左括号栈和星栈。每次遇到右括号时,先使用左括号栈内的元素,左括号栈为空时可以使用星栈,均为空则报错。
- 如果最终
left
和star
都有剩余,则挨个匹配,检查是否出现*(
的情况。因为不用考虑star
的剩余情况,只需要检查left
是否为空。 - 每个栈里边应放入
index
。
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元素
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,其实有相似之处,基本想法都是一致的。
但是实现的方法却不同,时间复杂度降低了很多,很巧妙,参考链接。
本文由 mmmwhy 创作,最后编辑时间为: May 6, 2019 at 09:43 pm