0678. 有效的括号字符串 #
- 标签:栈、贪心、字符串、动态规划
- 难度:中等
题目大意 #
描述:给定一个只包含三种字符的字符串:(
,)
和 *
。有效的括号字符串具有如下规则:
- 任何左括号
(
必须有相应的右括号)
。 - 任何右括号
)
必须有相应的左括号(
。 - 左括号
(
必须在对应的右括号之前)
。 *
可以被视为单个右括号)
,或单个左括号(
,或一个空字符串。- 一个空字符串也被视为有效字符串。
要求:验证这个字符串是否为有效字符串。如果是,则返回 True
;否则,则返回 False
。
说明:
- 字符串大小将在
[1, 100]
范围内。
示例:
- 示例 1:
|
|
解题思路 #
思路 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:复杂度分析 #
- 时间复杂度:$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)$)代码 #
|
|
思路 2:复杂度分析 #
- 时间复杂度:$O(n^2)$。两重循环遍历的时间复杂度是 $O(n^2)$。
- 空间复杂度:$O(n^2)$。用到了二维数组保存状态,所以总体空间复杂度为 $O(n^2)$。