javascript - 找到要在括号字符串的开头或结尾添加的最少括号以使其平衡

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