javascript - 算法:优化 'balancing brackets'

Question

有人向我提出以下问题...

给定字符串“( { [ } ] )”中的 N 个不同的左括号和右括号，检查字符串是否有匹配的括号。如果大括号匹配则返回 true，否则返回 false。

这是我想出的答案...

function braceeql(braces){
  var leftpar = 0; 
  var rightpar = 0; 
  var leftbrace = 0;
  var rightbrace = 0;
  var leftcurl = 0;
  var rightcurl = 0;

  for(var index = 0; index < braces.length; index++){
    if(braces[index] == ')'){
      leftpar += 1;
    }else if(braces[index] == '('){
      rightpar += 1;
    }else if(braces[index] == '['){
      leftbrace += 1;
    }else if(braces[index] == ']'){
      rightbrace += 1;
    }else if(braces[index] == '{'){
      leftcurl += 1;
    }else if(braces[index] == '}'){
      rightcurl += 1;
    }
  }
  if(leftcurl == rightcurl && leftbrace == rightbrace && leftpar == rightpar){
    console.log(true)
  }else{
    console.log(false)
  }
}

这是一段非常丰富的代码，但它确实有效。我看到了关于其他人如何解决这个问题的不同意见，但我想知道是否有更好/更干净的方法来解决这个算法而不损害大 O？

我非常愿意接受建议和其他看待这个问题的方法。

Answer 1

使用堆栈

以下解决方案的时间复杂度为 O(n)

function isBalanced(str) {
  const map = {
    '(': ')',
    '[': ']',
    '{': '}',
  };
  const closing = Object.values(map);
  const stack = [];
        
  for (let char of str) {
    if (map[char]) {
      stack.push(char);
    } else if (closing.includes(char) && char !== map[stack.pop()]) {
      return false;
    }
  }
  return !stack.length;
}