leetcode-678-有效的括号字符串
[博客链接]
[题目链接]
[github地址]
[题目描述]
给定一个只包含三种字符的字符串：（ ，） 和 *，写一个函数来检验这个字符串是否为有效字符串。有效字符串具有如下规则：
任何左括号 ( 必须有相应的右括号 )。
任何右括号 ) 必须有相应的左括号 ( 。
左括号 ( 必须在对应的右括号之前 )。
* 可以被视为单个右括号 ) ，或单个左括号 ( ，或一个空字符串。
一个空字符串也被视为有效字符串。
示例 1:
输入: "()"
输出: True
复制代码示例 2:
输入: "(*)"
输出: True
复制代码示例 3:
输入: "(*))"
输出: True
复制代码注意:
字符串大小将在 [1，100] 范围内。
思路一：动态规划
- 其实最开始做这种字符串匹配的问题大家考虑的可能都是通过栈来处理
- 本篇文章后面也会给出栈的解决方案
- 但是这种题其实dp解决起来反而会容易很多
- 所以大家之后遇到类似这种的括号匹配可以第一时间想到动态规划，而非栈操作
- 相对少了很多入栈和出栈的操作，稍微降低了了一些理解成本
- 本题的动态规划有两种思路，其中第一种思路较为容易理解和想到
- 定义dp方程dp[i][j]表示的是从下标i到下标j是否满足字符串匹配规律
- 我们可以发现有如下几种情况考虑
- s.charAt(i) == * 时 dp[i][i] = true
- dp[i][j] = (s.charAt(i+1)=='('||s.charAt(i+1)=='*')&& (s.charAt(j-1)==')'||s.charAt(j-1)=='*')
- dp[i][j] = dp[i][k]&&dp[k+1][j]
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[i-1][i]的匹配
for (int i = 1; i < n; i++) {
dp[i - 1][i] = ((s.charAt(i - 1) == '(' || s.charAt(i - 1) == '*') && (s.charAt(i) == ')' || s.charAt(i) == '*'));
}
//更新dp[i][j]
for (int i = n - 3; i >= 0; i--) {
char c1 = s.charAt(i);
for (int j = i + 2; j < n; j++) {
char c2 = s.charAt(j);
if ((c1 == '(' || c1 == '*') && (c2 == ')' || c2 == '*')) {
dp[i][j] = dp[i + 1][j - 1];
}
for (int k = i; k < j && !dp[i][j]; k++) {
dp[i][j] = dp[i][k] && dp[k + 1][j];
}
}
}
return dp[0][n-1];
}
复制代码- 时间复杂度O(
) - 空间复杂度O(
)
思路二：动态规划
- 定义dp[i][j] 表示前i个字符串需要补齐j个有括号才能满足要求
- 这个定义非常重要是理解转移方程的根本
- dp[0][0] = true
- 考虑转移过程
- 当s.charAt(i) = '(' 的时候，如果dp[i][j] == true,那么dp[i-1][j-1]==true,反之亦然（充要条件）
- 按照转移方程可以理解为，dp[i][j]表示需要有j个右括号的补齐
- 当 i==‘(’ 的时候，前i-1个字符串则只需要j-1个右括号补齐
- 当s.charAt(i) = ')' 的时候，如果dp[i][j] == true,那么dp[i-1][j+1]==true,反之亦然（充要条件）
- 当s.charAt(i) = '*' 的时候，如果dp[i][j] == true的条件就是三种情况有一种满足即可那么dp[i-1][j+1]==true||dp[i-1][j-1]==true||dp[i-1][j]==true,反之亦然（充要条件）
public boolean checkValidString(String s) {
int n = s.length();
boolean[][] dp = new boolean[n+1][n+1];
dp[0][0] = true;
for (int i = 1; i <= n; i++) {
int c1 = s.charAt(i-1);
for (int j = 0; j <= i; j++) {
if (c1 == '(') {
if (j > 0) {
dp[i][j] = dp[i - 1][j - 1];
}
} else if (c1 == ')') {
if (j < i) {
dp[i][j] = dp[i - 1][j + 1];
}
} else {
dp[i][j] = dp[i - 1][j];
if (j > 0) {
dp[i][j] |= dp[i - 1][j - 1];
}
if (j < i) {
dp[i][j] |= dp[i - 1][j + 1];
}
}
}
}
return dp[n][0];
}
复制代码- 时间复杂度O(
) - 空间复杂度O(
)
思路三：双栈模拟
- 这种字符串匹配大家最先想到的一定是栈来处理
- 本题因为存在*所以单独的栈是不好用的，我们需要两个栈存储*
- 因为存在先后顺序的原因可能会导致字符串不匹配，所以栈内需要存储下标索引
- 先判断所有右括号是否能够被左括号处理
- 如果不能拿前面的*号处理
- 最后剩余的左括号和*两个栈判断下标，左括号下标要小于*下标
public boolean checkValidString(String s) {
Stack<Integer> left = new Stack<>();
Stack<Integer> star = new Stack<>();
char[] chars = s.toCharArray();
for (int i = 0; i < chars.length; i++) {
if (chars[i] == '('){
left.push(i);
}else if (chars[i] == '*'){
star.push(i);
}else{
if (!left.isEmpty()){
left.pop();
}else if (!star.isEmpty()){
star.pop();
}else{
return false;
}
}
}
//判断左括号是否能找到所有对称括号
while (!left.isEmpty()&& !star.isEmpty()){
if (left.pop()> star.pop()){
return false;
}
}
return left.isEmpty();
}
复制代码- 时间复杂度O(
) - 空间复杂度O(
)
思路四：数字模拟
- 三叶大佬的模拟思路很好玩
- 我们将 '(' 看作得分+1，')' 看作得分-1
- 我们定义一个得分区间上下界(l,r)
- l表示最低得分，r表示最高得分
- 当出现左括号的时候，上界和下届同时++
- 当出现右括号的时候，上界和下届同时--
- 当出现*的时候，代表他有可能是左括号也有可能是有括号，当为右括号的时候下界--，当为左括号的时候上界++，
- 同时l不能为负值，因为如果l为负值，代表右括号过多，*号必然不可能当作右括号减少下界
- 当l>r的时候代表右括号过多，无法满足，因此可以直接返回false
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(0, l);
if (l > r) return false;
}
return l == 0;
}
复制代码- 时间复杂度O(
) - 空间复杂度O(
)
思路五：双向扫描
- 我们双向扫描字符串
- 从左往右扫描的时候判断只有右括号代表--，其余都是++，含义可以理解为消除掉左括号，将*看作左括号
- 从右往左扫描的时候判断只有左括号代表--，其余都是++，含义可以理解为消除掉右括号，将*看作右括号
public boolean checkValidString(String s) {
int l = 0, r = 0, n = s.length();
for (int i = 0; i < n; i++) {
l += s.charAt(i) == ')' ? -1 : 1;
r += s.charAt(n - i - 1) == '(' ? -1 : 1;
if (l < 0 || r < 0) {
return false;
}
}
return true;
}
复制代码- 时间复杂度O(
) - 空间复杂度O(
)
近期评论