0678. 有效的括号字符串

0678. 有效的括号字符串 #

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

题目大意 #

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

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

要求:验证这个字符串是否为有效字符串。如果是,则返回 True;否则,则返回 False

说明

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

示例

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

 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)$。
本站总访问量  次  |  您是本站第  位访问者