678-有效的括号字符串(Valid Parenthesis String)

原文链接: https://leetcode-cn.com/problems/valid-parenthesis-string

英文原文

Given a string s containing only three types of characters: '(', ')' and '*', return true if s is valid.

The following rules define a valid string:

Any left parenthesis '(' must have a corresponding right parenthesis ')'.
Any right parenthesis ')' must have a corresponding left parenthesis '('.
Left parenthesis '(' must go before the corresponding right parenthesis ')'.
'*' could be treated as a single right parenthesis ')' or a single left parenthesis '(' or an empty string "".

Example 1:

Input: s = "()"
Output: true

Example 2:

Input: s = "(*)"
Output: true

Example 3:

Input: s = "(*))"
Output: true

Constraints:

1 <= s.length <= 100
s[i] is '(', ')' or '*'.

中文题目

给定一个只包含三种字符的字符串：（ ，） 和 *，写一个函数来检验这个字符串是否为有效字符串。有效字符串具有如下规则：

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

示例 1:

输入: "()"
输出: True

示例 2:

输入: "(*)"
输出: True

示例 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]$。

代码：

[]
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$。

代码：

[]
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)$

其他「括号问题」内容

今天份送书营业中，戳这里进行了解 ~

题目	题解	难度	推荐指数
20. 有效的括号	LeetCode 题解链接	简单	🤩🤩🤩🤩🤩
22. 括号生成	LeetCode 题解链接	中等	🤩🤩🤩🤩
32. 最长有效括号	LeetCode 题解链接	困难	🤩🤩🤩🤩
301. 删除无效的括号	LeetCode 题解链接	困难	🤩🤩🤩🤩
678. 有效的括号字符串	LeetCode 题解链接	中等	🤩🤩🤩🤩🤩

注：以上目录整理来自 wiki，任何形式的转载引用请保留出处。

最后

如果有帮助到你，请给题解点个赞和收藏，让更多的人看到 ~ (“▔□▔)/

也欢迎你关注我（公主号后台回复「送书」即可参与长期看题解学算法送实体书活动）或加入「组队打卡」小群，提供写「证明」&「思路」的高质量题解。

所有题解已经加入刷题指南，欢迎 star 哦 ~

统计信息

通过次数	提交次数	AC比率
45661	118417	38.6%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言

相似题目

题目	难度
特殊的二进制序列	困难

凤起丶宛南

从来没有真正的绝境，只有心灵的迷途