gistfile1.txt

BALANCED BRACKETS 

// Write a function that takes in a string made up of brackets
// ("(", "[", "{") and other optional characters.  The function should
// return a boolean representing whether or not the string is balanced
// in regards to brackets.  A string is said to be balanced if it has as many
// opening brackets of a given type as it has closing brackets of that type
// and if no bracket is unmatched.  Note that a closing bracket cannot
// match a corresponding opening bracket that comes after it.  Similarly,
// brackets cannot overlap each other as in '[(])'


// HINT 1
// If you iterate through the input string one character at a time, there are
// two scenarios in which the string will be unbalanced: either you run into a
// closing bracket with no prior matching opening bracket or you get to the
// end of the string with some opening brackets that haven't been matched.
// Can you use an auxiliary data structure to keep track of all the brackets
// and efficiently check if you run into an unbalanced scenario at every iteration

// Hint2
// Consider using a stack to store opening brackets as you traverse the string.
// The last-in-first-out property of the stack should allow you to match
// any closing brackets that you run into against the most recent opening
// bracket, if one exists, in which case you can simply pop it out of the stack. How can you check that there are no 
// unmatched opening braces
// once you've finished traversing the string?

// O(n) time and O(n) space where n is the length of the input array.


const balancedBrackets = string => {
  const openingBrackets = '([{';
  const closingBrackets = ')]}';
  const matchingBrackets = {
    ')': '(',
    '}': '{',
    ']': '[',
  };
  const stack = [];
  for (let i = 0; i < string.length; i++) {
    if (openingBrackets.includes(string[i])) {
      stack.push(string[i]);
    } else if (closingBrackets.includes(string[i])) {
      if (stack.length === 0) {
        return false;
      }
      if (stack[stack.length - 1] === matchingBrackets[string[i]]) {
        stack.pop();
      } else {
        return false;
      }
    }
  }
  return stack.length === 0;
};