- 有效的括号字符串
【问题描述】
给你一个只包含三种字符的字符串，支持的字符类型分别是 ‘(’、‘)’ 和 ‘*’。请你检验这个字符串是否为有效字符串，如果是有效字符串返回 true 。
有效字符串符合如下规则：
任何左括号 '(' 必须有相应的右括号 ')'。
任何右括号 ')' 必须有相应的左括号 '(' 。
左括号 '(' 必须在对应的右括号之前 ')'。
'*' 可以被视为单个右括号 ')' ，或单个左括号 '(' ，或一个空字符串。
一个空字符串也被视为有效字符串。
示例 1：
输入：s = “()”
输出：true
示例 2：
输入：s = “(*)”
输出：true
示例 3：
输入：s = “(*))”
输出：true
【思路】
我们可以使用动态规划的思路来解决上述问题。我们可以定义一个二维数组 dp，其中 dp[i][j] 表示从字符串的第 i 个字符到第 j 个字符（闭区间）是否为有效字符串。
根据题目规则，我们可以得出以下状态转移方程：
1、当 s[i] 和 s[j] 分别为 ‘(’ 和 ‘)’ 时，dp[i][j] 可以为有效字符串的条件是 dp[i+1][j-1] 为有效字符串。
2、当 s[i] 和 s[j] 同时为 ‘*’ 时，dp[i][j] 可以为有效字符串的条件是：
内部存在一个分割点k，使得 dp[i][k] && dp[k+1][j] 同时为有效的括号字符串。
【Java代码】：
public boolean checkValidString(String s) {
int n = s.length();
boolean[][] dp = new boolean[n][n];
// 初始化对角线，单个字符为 '*' 时为有效字符串
for (int i = 0; i < n; i++) {
if (s.charAt(i) == '*') {
dp[i][i] = true;
}
}
// 填充 dp 数组
for (int len = 2; len <= n; len++) {
for (int i = 0; i <= n - len; i++) {
int j = i + len - 1;
char c1 = s.charAt(i);
char c2 = s.charAt(j);
//注意这里，外层()和 *)和（* 都是可以满足匹配的。因此只用考虑子问题即可
if ((c1 == '(' && c2 == ')') || (c1 == '*' && c2 == ')') || (c1 == '(' && c2 == '*')) {
if (len == 2 || dp[i+1][j-1]) {
dp[i][j] = true;
}
}
// 如果i, j同时为*。那么这时候就去枚举内部的分割点k
//看是否能把字符串分割成两个有效的括号字符串。转化为子问题。
for (int k = i; k < j && !dp[i][j]; k++) {
if (dp[i][k] && dp[k+1][j]) {
dp[i][j] = true;
}
}
}
}
return dp[0][n-1];
}
【注】：
在这个代码设计过程中，双重循环的参数也是一个需要仔细思考的点。代码中的两个循环是为了遍历所有可能的子串长度和起始位置。
因为这个问题中，大串的结果依赖于小串，所以我们必须先把小串的问题解决。
因此第一个循环 for (int len = 2; len <= n; len++) 控制子串的长度 len，从长度为 2 开始，逐渐增加到整个字符串的长度 n。这是因为一个有效的括号序列至少包含一对括号，所以子串的长度必须大于等于 2。
第二个循环 for (int i = 0; i <= n - len; i++) 控制子串的起始位置 i，从字符串的开头开始，逐渐向右移动。由于子串的长度为 len，所以起始位置的最大值为 n - len，以确保子串不会超出字符串的边界。文章来源：https://www.toymoban.com/news/detail-642890.html
通过这两个循环的组合，可以遍历到字符串中的所有可能的子串，从而进行动态规划的状态转移。循环的设计使得算法能够逐步扩展子串的长度，并按顺序计算出所有子问题的解，以便最终得到整个字符串的解。文章来源地址https://www.toymoban.com/news/detail-642890.html
到了这里，关于Leetcode 678. 有效的括号字符串的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
