678. 有效的括号字符串
给定一个只包含三种字符的字符串：（ ，） 和*，写一个函数来检验这个字符串是否为有效字符串。有效字符串具有如下规则：
1、任何左括号( 必须有相应的右括号 )。
2、任何右括号 ) 必须有相应的左括号( 。
3、左括号 ( 必须在对应的右括号之前 )。
4、*可以被视为单个右括号 ) ，或单个左括号 ( ，或一个空字符串。
5、一个空字符串也被视为有效字符串。
示例：”()” -> True；”(*)” -> True；
”(*))” -> True
- 1、方法一：自己写的算法，不太好，但是能够通过所有测试用例
核心逻辑：消消乐
遍历所有左括号下标，找对应的右括号/*号 -> 找到就删除对应下标 -> 遍历完左括号后剩余的右括号找 *号
2个特别注意点：
1⃣️遍历所有左括号下标，要逆序查找【正序会出现下标比较大的 右括号/* 被消掉了】
2⃣️如果可以和左括号对应的 右括号/* 数组 都存在的时候，优先消除右括号
时间复杂度：O(n)，空间复杂度：xx
var checkValidString = function(s) {
let res = true;
let leftArr = [];
let rightArr = [];
let xingArr = [];
for(let i = 0; i < s.length ; i++) {
s[i] === "(" && leftArr.push(i);
s[i] === ")" && rightArr.push(i);
s[i] === "*" && xingArr.push(i);
}
// 遍历所有左括号下标，要逆序查找 --> 防止靠后的左括号找不到对应的 */右括号
leftArr.reverse().forEach((left, leftIdx) => {
// 找到右括号中符合条件的下标
let rightFindIdx = rightArr.findIndex(right => right >= left);
// 找到*数组中符合条件的下标
let xingFindIdx = xingArr.findIndex(xing => xing >= left);
// 两个数组都不存在
if((rightFindIdx < 0) && (xingFindIdx < 0)) {
res = false;
}
// 如果 *数组/右括号 中只找到一个
if ((rightFindIdx < 0) && (xingFindIdx > -1)) {
xingArr.splice(xingFindIdx,1);
}
if ((rightFindIdx > -1) && (xingFindIdx < 0)) {
rightArr.splice(xingFindIdx,1);
}
// 优先取右括号 --> 防止右括号过多剩余，导致找不到对应的左括号
if ((rightFindIdx > -1) && (xingFindIdx > -1)) {
rightArr.splice(rightFindIdx,1);
}
})
// 如果遍历完左括号数组，右括号还有剩余
if (res && rightArr.length > 0) {
rightArr.forEach((other, otherIdx) => {
let xingRightIdx = xingArr.findIndex(xing => xing <= other);
// 如果*数组中存在符合条件的下标，继续遍历右括号数组
if(xingRightIdx > -1) {
xingArr.splice(xingRightIdx,1);
} else {
// 如果*数组不存在，那么剩余的右括号就找不到对应的右括号了
res = false;
}
})
}
return res;
};
- 2、在评论里面翻到的方法
核心思想： *号既然可以替换为任意()，那么就计算一下全部替换成(或者)时有没有剩余左括号
时间复杂度：O(n)，空间复杂度：xx
// 方法二：
var checkValidString = (s) => {
//s: "((*" (三种情况)
//s:"(((" count++
//s:"(()" count--
//s:"(( " count
let len = s.length;
let minCount = 0;//最少有多少个'('
let maxCount = 0;//最多有多少个'('
for(let i=0;i<len;i++)
{
if( s[i] === '(' ) {
maxCount++;
minCount++;
} else if ( s[i] === ')' ) {
maxCount--;
minCount--;
} else if ( s[i] === '*' ) {
maxCount++; //'*' 为 '('
minCount--; //'*' 为 ')'
//'*' 为 空格都不变
}
if( maxCount < 0) {
return false;
}
//当第一个为'*'时只能用作'(' 或 空（空可以忽略）
if( minCount < 0) {
minCount = 0;
}
}
return minCount === 0;
}
- 3、在评论区看到的算法，也算是对我第一个算法的优化
核心思想：利用栈的后进先出实现 –> (和*分别push到两个栈中，遇到)就弹出一个 -> 直到最后剩余的右括号一定是已经遍历完了 -> 剩余的(再找*中有没有可以对应的
时间复杂度：O(n)，空间复杂度：xx
var checkValidString = (s) => {
let pos = true;
let leftStack = [];
let rightStack = [];
let xingStack = [];
for(let i = 0; pos && i < s.length; i++) {
if(s[i] === '(') {
leftStack.push(i);
}
if(s[i] === '*') {
xingStack.push(i);
}
if(s[i] === ')') {
// 左栈中存在，则弹出
if (leftStack.length) {
leftStack.pop();
} else {
// 左栈中不存在，星栈中存在
if(xingStack.length) {
xingStack.pop();
} else {
// 左栈/星栈中都不存在
pos = false;
}
}
}
}
// 如果左括号存在剩余
leftStack.forEach((left, index) => {
let xingIdx = xingStack && xingStack.findIndex(xing => xing >= left);
if(xingIdx > -1) {
xingStack.splice(xingIdx, 1);
} else {
pos = false;
}
})
return pos
}