算法：优化“平衡括号”

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;
}

Answer 2

好吧，首先，您的解决方案似乎并不涵盖像 )(][ 或 ({)} 这样的情况（我不确定您是否被要求这样做，但据我所知，这个玩具问题要求这样做）

这是我一年多前提出的这个玩具问题的解决方案，但它看起来更快（如果不匹配，它会更早停止，有更少的 if 和 else）并且重复的代码更少，但我不确定是否更干净，因为从新手的角度来看，ifs和else更容易理解

var braceeql = function(braces){
  var stack = {};
  var size = 0;
  var beginners = ['(', '[', '{'];
  var enders = [')', ']', '}'];
  for(var i = 0; i < braces.length; i++){
    if( beginners.indexOf(braces[i]) !== -1 ){
      stack[size] = braces[i];
      size++;
    } else if( enders.indexOf(braces[i]) !== -1 ){
      if(size === 0) { return false; }
      var index = enders.indexOf(braces[i]);
      if(stack[size-1] === beginners[index] ){
        size --;
      } else {
        return false;
      }
    }
  }

  return size === 0;
};