找到要在参数字符串的开头或结尾添加的最小参数，以使其平衡

Question

需要在开头或结尾添加所需的最小括号来平衡括号。 例- 如果I = "(((((((">则R = [0,1]

我创建了一个解决方案，例如

function bPar(s){
let stack1 = [];
let result = [0,0];
s.split("").forEach(x=>{
if(x==="("){
stack1.push("(");
}else if(x===")"){
if(stack1[stack1.length-1]==="("){
stack1.pop();
}else{
stack1.push(")")
}
}
})
stack1.forEach(x=>{
if(x=="("){
result[1]=result[1]+1;
}else if(x==")"){
result[0]=result[0]+1;
}
})
return result;
}
console.log(bPar("(()(())"));

但我认为时间复杂度更高。他们有更好的方法吗？

Answer 1

您可以跟踪当前打开括号的数量，而不是堆栈数组。如果您在该数字为 0 时遇到)，请在所需的其他(s 数中添加一个数字：

function bPar(s){
let additionalOpensNeededAtBegin = 0;
let openCount = 0;
for (const char of s) {
if (char === '(') openCount++;
else {
if (openCount === 0) additionalOpensNeededAtBegin++;
else openCount--;
}
}
return [additionalOpensNeededAtBegin, openCount];
}
console.log(bPar("(()(())"));
console.log(bPar("((((("));
console.log(bPar(")))))"));
console.log(bPar(")(((("));
console.log(bPar("))))("));
console.log(bPar("(())"));