题目

难度：★★★☆☆
类型：数组
方法：动态规划

力扣链接请移步本题传送门
更多力扣中等题的解决方案请移步力扣中等题目录

给定一个只包含三种字符的字符串：（ ，） 和 *，写一个函数来检验这个字符串是否为有效字符串。有效字符串具有如下规则：

任何左括号 ( 必须有相应的右括号 )。
任何右括号 ) 必须有相应的左括号 ( 。
左括号 ( 必须在对应的右括号之前 )。

• 可以被视为单个右括号 ) ，或单个左括号 ( ，或一个空字符串。
  一个空字符串也被视为有效字符串。

示例 1:

输入: "()"
输出: True

示例 2:

输入: "(*)"
输出: True

示例 3:

输入: "(*))"
输出: True

注意:

字符串大小将在 [1，100] 范围内。

解答

这里介绍一种时间复杂度为N的贪心算法。

我们定义两个计数器left和right，用于统计字符串中左括号与右括号出现的次数。

从左往右遍历字符串，只要遇到非右括号的字符，我们就将其认为是左括号（因为星花可以代表任意括号），在遍历过程中，只要遇到左括号以及星号演变的左括号的个数已经不足以凑够右括号的个数时，就可以认定该字符串是非法的。

但是，只有左括号的判定是不够的，万一左括号的个数太多也不行。因此，需要进行一个关于右括号的判断，但是要注意这次遍历需要反向的。

以上两个遍历均通过，即可认为字符串是合法的。

class Solution:
    def checkValidString(self, s: str) -> bool:
        left, right = 0, 0
        for i, c in enumerate(s):
            if c != ')':
                left += 1
            if left < i // 2:
                return False
        for i, c in enumerate(reversed(s)):
            if c != '(':
                right += 1
            if right <i // 2:
                return False
        return True

如有疑问或建议，欢迎评论区留言~

有关更多力扣中等题的python解决方案，请移步力扣中等题解析