题目
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