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

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

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

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

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，其实有相似之处，基本想法都是一致的。

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