括号有效性验证方法解析——面试算法问题求助

Hey there! Let's walk through how to implement this bracket validation function clearly, covering all the edge cases you mentioned.

Core Idea #

Since we're only dealing with round brackets (()), a simple counter-based approach works perfectly (no need for a full stack unless we had multiple bracket types like [] or {}). The key is to track the balance between opening and closing brackets as we iterate through the string.

Logic Breakdown #

Let's break down the rules we need to enforce:

• Every opening bracket ( must have a corresponding closing bracket ) that comes after it.
• At no point should closing brackets outnumber opening ones (this catches cases like )( or ()()) early).
• By the end of the string, the total number of opening and closing brackets must be equal.

Here's how to translate that into code:

1. Initialize a balance counter to 0. This will track how many unclosed opening brackets we have.
2. Loop through each character in the input string:
   • If the character is (, increment balance (we have an unclosed opening bracket).
   • If the character is ), decrement balance (we're closing an opening bracket).
   • Critical check: If balance becomes negative at any point, return false immediately. This means we've encountered a closing bracket with no matching opening bracket before it.
3. After processing all characters, check if balance is 0. If yes, all brackets are properly matched; if not, there are unmatched opening brackets left.

Complete Code Implementation #

function validator(brackets) {
  let balance = 0;
  
  for (const char of brackets) {
    if (char === '(') {
      balance++;
    } else if (char === ')') {
      balance--;
      // If balance goes negative, we have an unmatched closing bracket
      if (balance < 0) {
        return false;
      }
    }
    // Note: If your input might have non-bracket characters, add a check to ignore them here
  }
  
  // Final check: all opening brackets must have been closed
  return balance === 0;
}

// Test cases from your question
const goodBrackets = '(((())))';
const badBrackets = '(()())))';
const veryBadBrackets = '(()())()))';

console.log(validator(goodBrackets)); // true
console.log(validator(badBrackets)); // false
console.log(validator(veryBadBrackets)); // false

Why This Works for Your Test Cases #

• goodBrackets: Every ( has a corresponding ) after it, balance ends at 0 → returns true.
• badBrackets: By the 7th character (extra )), balance drops to -1 → returns false early.
• veryBadBrackets: Similar to the above, balance goes negative before the end of the string → returns false.

This approach runs in O(n) time (we iterate through the string once) and uses O(1) space (only a single counter variable), making it efficient even for long strings.

内容的提问来源于stack exchange，提问作者Max Wolfen