One Pager Cheat Sheet

• You need to write a function that will check if the symbol pairings in a string of length up to 100000 that consists of [, ], {, }, (, ) follow the conditions of being correctly ordered, paired, and of the same kind, with an expected time complexity of O(n) and an expected space complexity of O(n).
• We should use a stack to keep track of incoming and outgoing symbols in order to maintain balance in a string.
• Using a counter to track the difference between opening and closing symbols is not sufficient since multiple types of symbols are involved and relative order matters.
• The items in a stack are inserted and removed according to the Last in, First out (LIFO) principle.
• Stack data structures provide an efficient way to parse strings of opening/closing symbols with O(1) push/pop operations.
• We pop() any opposite/pairwise symbols off the stack as we visualize the processing.
• A Last In, First Out (LIFO) data structure, such as a stack, can be used to solve various problems, including tracking function calls, validating brackets, calculating prefix expressions, and solving mazes.
• If the characters of a string do not match at any point, it is an invalid string.

This is our final solution.

To visualize the solution and step through the below code, click Visualize the Solution on the right-side menu or the VISUALIZE button in Interactive Mode.

xxxxxxxxxx

}

var assert = require('assert');

​

function validateSymbols(str) {

  let map = {

    ')': '(',

    ']': '[',

    '}': '{',

  };

  let stack = [];

  for (let i = 0; i < str.length; i++) {

    if (str[i] === '(' || str[i] === '[' || str[i] === '{') {

      stack.push(str[i]);

    } else {

      if (stack[stack.length - 1] === map[str[i]]) {

        stack.pop();

      } else return false;

    }

  }

  return stack.length === 0 ? true : false;

}

​

try {

  assertIsFunction(validateSymbols);

​

  console.log('PASSED: ' + '`validateSymbols` is a function');

} catch (err) {

  console.log(err);

}

​

try {

  assert.equal(validateSymbols('[]'), true);

​

Great job getting through this. Let's move on.

If you had any problems with this tutorial, check out the main forum thread here.