0678. 有效的括号字符串

• 标签：栈、贪心、字符串、动态规划
• 难度：中等

题目大意

描述：给定一个只包含三种字符的字符串：（ ，) 和 *。有效的括号字符串具有如下规则：

1. 任何左括号 ( 必须有相应的右括号 )。
2. 任何右括号 ) 必须有相应的左括号 (。
3. 左括号 ( 必须在对应的右括号之前 )。
4. * 可以被视为单个右括号 )，或单个左括号 (，或一个空字符串。
5. 一个空字符串也被视为有效字符串。

要求：验证这个字符串是否为有效字符串。如果是，则返回 True；否则，则返回 False。

说明：

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

示例：

• 示例 1：

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

解题思路

思路 1：动态规划（时间复杂度为 $O(n^3)$）

1. 划分阶段

按照子串的起始位置进行阶段划分。

2. 定义状态

定义状态 dp[i][j] 表示为：从下标 i 到下标 j 的子串是否为有效的括号字符串，其中 （$0 \le i < j < size$，$size$ 为字符串长度）。如果是则 dp[i][j] = True，否则，dp[i][j] = False。

3. 状态转移方程

长度大于 2 时，我们需要根据 s[i] 和 s[j] 的情况，以及子串中间的有效字符串情况来判断 dp[i][j]。

• 如果 s[i]、s[j] 分别表示左括号和右括号，或者为 '*'（此时 s[i]、s[j] 可以分别看做是左括号、右括号）。则如果 dp[i + 1][j - 1] == True 时，dp[i][j] = True。
• 如果可以将从下标 i 到下标 j 的子串从中间分开为两个有效字符串，则 dp[i][j] = True。即如果存在 $i \le k < j$，使得 dp[i][k] == True 并且 dp[k + 1][j] == True，则 dp[i][j] = True。

4. 初始条件

• 当子串的长度为 1，并且该字符串为 '*' 时，子串可看做是空字符串，此时子串是有效的括号字符串。
• 当子串的长度为 2 时，如果两个字符可以分别看做是左括号和右括号，子串可以看做是 "()"，此时子串是有效的括号字符串。

5. 最终结果

根据我们之前定义的状态，dp[i][j] 表示为：从下标 i 到下标 j 的子串是否为有效的括号字符串。则最终结果为 dp[0][size - 1]。

思路 1：动态规划（时间复杂度为 $O(n^3)$）代码

class Solution:
    def checkValidString(self, s: str) -> bool:
        size = len(s)
        dp = [[False for _ in range(size)] for _ in range(size)]

        for i in range(size):
            if s[i] == '*':
                dp[i][i] = True

        for i in range(1, size):
            if (s[i - 1] == '(' or s[i - 1] == '*') and (s[i] == ')' or s[i] == '*'):
                dp[i - 1][i] = True

        for i in range(size - 3, -1, -1):
            for j in range(i + 2, size):
                if (s[i] == '(' or s[i] == '*') and (s[j] == ')' or s[j] == '*'):
                    dp[i][j] = dp[i + 1][j - 1]
                for k in range(i, j):
                    if dp[i][j]:
                        break
                    dp[i][j] = dp[i][k] and dp[k + 1][j]

        return dp[0][size - 1]

思路 1：复杂度分析

• 时间复杂度：$O(n^3)$。三重循环遍历的时间复杂度是 $O(n^3)$。
• 空间复杂度：$O(n^2)$。用到了二维数组保存状态，所以总体空间复杂度为 $O(n^2)$。

思路 2：动态规划（时间复杂度为 $O(n^2)$）

1. 划分阶段

按照字符串的结束位置进行阶段划分。

2. 定义状态

定义状态 dp[i][j] 表示为：前 i 个字符能否通过补齐 j 个右括号成为有效的括号字符串。

3. 状态转移方程

1. 如果 s[i] == '('，则如果前 i - 1 个字符通过补齐 j - 1 个右括号成为有效的括号字符串，则前 i 个字符就能通过补齐 j 个右括号成为有效的括号字符串（比前 i - 1 个字符需要多补一个右括号）。也就是说，如果 s[i] == '(' 并且 dp[i - 1][j - 1] == True，则 dp[i][j] = True。
2. 如果 s[i] == ')'，则如果前 i - 1 个字符通过补齐 j + 1 个右括号成为有效的括号字符串，则前 i 个字符就能通过补齐 j 个右括号成为有效的括号字符串（比前 i - 1 个字符需要少补一个右括号）。也就是说，如果 s[i] == ')' 并且 dp[i - 1][j + 1] == True，则 dp[i][j] = True。
3. 如果 s[i] == '*'，而 '*' 可以表示空字符串、左括号或者右括号，则 dp[i][j] 取决于这三种情况，只要有一种情况为 True，则 dp[i][j] = True。也就是说，如果 s[i] == '*'，则 dp[i][j] = dp[i - 1][j] or dp[i - 1][j - 1]。

4. 初始条件

• 0 个字符可以通过补齐 0 个右括号成为有效的括号字符串（空字符串），即 dp[0][0] = 0。

5. 最终结果

根据我们之前定义的状态，dp[i][j] 表示为：前 i 个字符能否通过补齐 j 个右括号成为有效的括号字符串。。则最终结果为 dp[size][0]。

思路 2：动态规划（时间复杂度为 $O(n^2)$）代码

class Solution:
    def checkValidString(self, s: str) -> bool:
        size = len(s)
        dp = [[False for _ in range(size + 1)] for _ in range(size + 1)]
        dp[0][0] = True
        for i in range(1, size + 1):
            for j in range(i + 1):
                if s[i - 1] == '(':
                    if j > 0:
                        dp[i][j] = dp[i - 1][j - 1]
                elif s[i - 1] == ')':
                    if j < i:
                        dp[i][j] = dp[i - 1][j + 1]
                else:
                    dp[i][j] = dp[i - 1][j]
                    if j > 0:
                        dp[i][j] = dp[i][j] or dp[i - 1][j - 1]
                    if j < i:
                        dp[i][j] = dp[i][j] or dp[i - 1][j + 1]

        return dp[size][0]

思路 2：复杂度分析

• 时间复杂度：$O(n^2)$。两重循环遍历的时间复杂度是 $O(n^2)$。
• 空间复杂度：$O(n^2)$。用到了二维数组保存状态，所以总体空间复杂度为 $O(n^2)$。