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

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

标签： javascriptdata-structures

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