LC 678. 有效的括号字符串

题目描述

这是 LeetCode 上的 678. 有效的括号字符串 ，难度为 中等。

给定一个只包含三种字符的字符串：( ，) 和 *，写一个函数来检验这个字符串是否为有效字符串。

有效字符串具有如下规则：

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

示例 1:

1
2
3
输入: "()"

输出: True

示例 2:

1
2
3
输入: "(*)"

输出: True

示例 3:
1
2
3
输入: "(*))"

输出: True

注意:

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

动态规划

定义 $f[i][j]$ 为考虑前 $i$ 个字符（字符下标从 $1$ 开始），能否与 $j$ 个右括号形成合法括号序列。

起始时只有 $f[0][0]$ 为 $true$，最终答案为 $f[n][0]$。

不失一般性的考虑 $f[i][j]$ 该如何转移：

  • 当前字符为 ( : 如果 $f[i][j]$ 为 $true$，必然有 $f[i - 1][j - 1]$ 为 $true$，反之亦然。即有 $f[i][j] = f[i - 1][j - 1]$；
  • 当前字符为 ) : 如果 $f[i][j]$ 为 $true$，必然有 $f[i - 1][j + 1]$ 为 $true$，反之亦然。即有 $f[i][j] = f[i - 1][j + 1]$；
  • 当前字符为 * : 根据 * 代指的符号不同，分为三种情况，只有有一种情况为 $true$ 即可。即有 $f[i][j] = f[i - 1][j - 1] ∨ f[i - 1][j + 1] ∨ f[i - 1][j]$。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public boolean checkValidString(String s) {
        int n = s.length();
        boolean[][] f = new boolean[n + 1][n + 1];
        f[0][0] = true;
        for (int i = 1; i <= n; i++) {
            char c = s.charAt(i - 1);
            for (int j = 0; j <= i; j++) {
                if (c == '(') {
                    if (j - 1 >= 0) f[i][j] = f[i - 1][j - 1];
                } else if (c == ')') {
                    if (j + 1 <= i) f[i][j] = f[i - 1][j + 1];
                } else {
                    f[i][j] = f[i - 1][j];
                    if (j - 1 >= 0) f[i][j] |= f[i - 1][j - 1];
                    if (j + 1 <= i) f[i][j] |= f[i - 1][j + 1];
                }
            }
        }
        return f[n][0];
    }
}

  • 时间复杂度：$O(n^2)$
  • 空间复杂度：$O(n^2)$

模拟

通过解法一，我们进一步发现，对于某个 $f[i][x]$ 而言（即动规数组中的某一行），值为 $true$ 的必然为连续一段。

即 由于存在可变化的 * 符号，因此考虑在考虑前 $i$ 个字符，其能与消耗的左括号的数量具有明确的「上界与下界」。且当前上界与下界的变化，仅取决于「当前为何种字符」，以及「处理上一个字符时上界与下界为多少」。

但直接记录所能消耗的左括号上限和下限需要处理较多的边界问题。

我们可以使用与（题解）301. 删除无效的括号 类似的思路：

令左括号的得分为 $1$；右括号的得分为 $-1$。那么对于合法的方案而言，必定满足最终得分为 $0$。

同时由于本题存在 *，因此我们需要记录得分的区间区间是多少，而不仅是一个具体的得分。

具体的，使用两个变量 l 和 r 分别表示「最低得分」和「最高得分」。

根据当前处理到的字符进行分情况讨论：

  • 当前字符为 ( : l 和 r 同时加一；
  • 当前字符为 ) : l 和 r 同时减一；
  • 当前字符为 * : 如果 * 代指成 ( 的话，l 和 r 都进行加一；如果 * 代指成 ) 的话，l 和 r 都进行减一；如果 * 不变的话，l 和 r 均不发生变化。因此总的 l 的变化为减一，总的 r 的变化为加一。

需要注意的是，在匹配过程中如果 l 为负数，需要重置为 $0$，因为如果当前序列本身为不合法括号序列的话，增加 ( 必然还是不合法。同时，当出现 l > r 说明上界为负数，即右括号过多，必然为非合法方案，返回 $false$。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public boolean checkValidString(String s) {
        int l = 0, r = 0;
        for (char c : s.toCharArray()) {
            if (c == '(') {
                l++; r++;
            } else if (c == ')') {
                l--; r--;
            } else {
                l--; r++;
            }
            l = Math.max(l, 0);
            if (l > r) return false;
        }
        return l == 0;
    }
}

  • 时间复杂度：$O(n)$
  • 空间复杂度：$O(1)$

最后

这是我们「刷穿 LeetCode」系列文章的第 No.678 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。