题目描述
给定一个只包含三种字符的字符串:(
,)
和 *
,写一个函数来检验这个字符串是否为有效字符串。有效字符串具有如下规则:
- 任何左括号
(
必须有相应的右括号)
。 - 任何右括号
)
必须有相应的左括号(
。 - 左括号
(
必须在对应的右括号之前)
。 *
可以被视为单个右括号)
,或单个左括号(
,或一个空字符串。- 一个空字符串也被视为有效字符串。
样例
输入: "()"
输出: True
输入: "(*)"
输出: True
输入: "(*))"
输出: True
提示
- 字符串大小将在
[1,100]
范围内。
算法1
(动态规划) $O(n^2)$
- 设 $f(i, j)$ 表示前 $i$ 个字符,是否能组成剩余 $j$ 个左括号的情况,字符串的下标从 1 开始。
- 初始时,$f(0, 0) = true$,其余为 $false$。
- 转移时,如果当前字符为
(
,则 $f(i, j) = f(i - 1, j - 1)$;如果当前字符为)
,则 $f(i, j) = f(i - 1, j + 1)$;如果为*
,则 $f(i, j) = f(i - 1, j) \text{ or } f(i - 1, j - 1) \text{ or } f(i - 1, j + 1)$。 - 最终答案为 $f(n, 0)$。
时间复杂度
- 状态数为 $O(n^2)$,每次转移仅需要常数时间,故总时间复杂度为 $O(n^2)$。
空间复杂度
- 需要额外的 $O(n^2)$ 的空间记录状态,但可以通过滚动数组压缩至 $O(n)$。
C++ 代码
class Solution {
public:
bool checkValidString(string s) {
int n = s.length();
vector<vector<bool>> f(n + 1, vector<bool>(n + 1, false));
f[0][0] = true;
for (int i = 1; i <= n; i++) {
char c = s[i - 1];
for (int j = 0; j <= i; j++) {
if (c == '(') {
if (j >= 1)
f[i][j] = f[i - 1][j - 1];
} else if (c == ')') {
if (j < i)
f[i][j] = f[i - 1][j + 1];
} else {
f[i][j] = f[i - 1][j];
if (j >= 1)
f[i][j] = f[i][j] || f[i - 1][j - 1];
if (j < i)
f[i][j] = f[i][j] || f[i - 1][j + 1];
}
}
}
return f[n][0];
}
};
算法2
(动态规划优化) $O(n)$
- 算法 1 中的计算中会有很多冗余。假设 $f(i, j)$ 中为 $true$ 的最小的 $j$ 为 $j_0$,最大的为 $j_1$,则 $j_0$ 到 $j_1$ 之间都为 $true$。
- 所以我们仅需要维护一个下界
lower
和一个上界upper
,初始时都为 0。 - 如果当前字符为
(
,则上下界都加 1;如果为)
,则下界减 1(但最低为 0),(如果上界为 0,则说明不合法,返回false
),上界减 1。如果当前字符为*
,则下界减 1,上界加 1。 - 最后判断下界是否为 0。
时间复杂度
- 仅遍历数组一次,故时间复杂度为 $O(n)$。
空间复杂度
- 仅需要常数的额外空间。
C++ 代码
class Solution {
public:
bool checkValidString(string s) {
int lower = 0, upper = 0;
for (char c : s)
if (c == '(') {
lower++;
upper++;
} else if (c == ')') {
lower = max(lower - 1, 0);
if (upper == 0)
return false;
upper--;
} else {
lower = max(lower - 1, 0);
upper++;
}
return lower == 0;
}
};
设 f(i,j)表示前i个字符,是否能组成剩余j个左括号的情况。为什么这样定义状态能把右括号多余的情况也考虑在内呢
另外(j < i)的判断条件,如果j=i-1的话,j+1,i-1就越界了,我修改成j-1<i发现也能过,好迷
这里剩余 $j$ 个左括号是剩余 $j$ 个左括号未匹配的情况下,如果遇到了一个右括号,而没有与之对应的左括号,则状态是非法的。
j + 1
不会越界,数组的范围是[0, n]
,长度为n + 1
。根据定义前i个字母不可能组成超过i个左括号,那么j维大于i维是不是就没意义了呢
没意义的状态显然是 false,所以不会造成转移错误
欧科