本文共 1632 字，大约阅读时间需要 5 分钟。

题目：（中等）

标签：字符串、贪心算法

LeetCode的Python执行用时随缘，只要时间复杂度没有明显差异，执行用时一般都在同一个量级，仅作参考意义。

解法一（情景模拟）：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-TvCqyEYc-1597649838789)(LeetCode题解(0678)]：截图1.png)

class Solution:    def checkValidString(self, s: str) -> bool:        stack = []        for ch in s:            if ch == ")":                idx = len(stack) - 1                while idx > -1:                    if stack[idx] == "(":                        break                    idx -= 1                if idx >= 0:                    stack.pop(idx)                elif len(stack) > 0:                    stack.pop()                else:                    return False            else:                stack.append(ch)        left_num = 0        for ch in stack:            if ch == "(":                left_num += 1            elif left_num > 0:                left_num -= 1        return left_num == 0

解法二（贪心算法）：

class Solution:    def checkValidString(self, s: str) -> bool:        min_left_num = 0        max_left_num = 0        for ch in s:            if ch == "(":                min_left_num += 1                max_left_num += 1            elif ch == "*":                if min_left_num > 0:                    min_left_num -= 1                max_left_num += 1            else:                if min_left_num > 0:                    min_left_num -= 1                max_left_num -= 1            if max_left_num < 0:                return False        return min_left_num == 0

转载地址：https://dataartist.blog.csdn.net/article/details/108057135 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！