678. Valid Parenthesis String
in

678. Valid Parenthesis String

?> with 0 comment

题目链接: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:

递归算法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

两个栈

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 记录所有当前左括号-右括号的差值

遍历结束,判断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

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

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

Responses

From now on, bravely dream and run toward that dream.
陕ICP备17001447号·苏公网安备 32059002001895号