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

Question

需要通过在开始或结束时添加最小所需括号来平衡括号。例如——如果我 = "(()(())" 那么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：

js prettyprint-override">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("(())"));