0678. 有效的括号字符串 #

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

题目大意 #

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

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

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

说明：

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

示例：

示例 1：

1
2


输入："(*)"
输出：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)$）代码 #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


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. 状态转移方程 #

如果 s[i] == '('，则如果前 i - 1 个字符通过补齐 j - 1 个右括号成为有效的括号字符串，则前 i 个字符就能通过补齐 j 个右括号成为有效的括号字符串（比前 i - 1 个字符需要多补一个右括号）。也就是说，如果 s[i] == '(' 并且 dp[i - 1][j - 1] == True，则 dp[i][j] = True。
如果 s[i] == ')'，则如果前 i - 1 个字符通过补齐 j + 1 个右括号成为有效的括号字符串，则前 i 个字符就能通过补齐 j 个右括号成为有效的括号字符串（比前 i - 1 个字符需要少补一个右括号）。也就是说，如果 s[i] == ')' 并且 dp[i - 1][j + 1] == True，则 dp[i][j] = True。
如果 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)$）代码 #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


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)$。