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 ofO(n)
and an expected space complexity ofO(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 wevisualize
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
56
}
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);
​
OUTPUT
:001 > Cmd/Ctrl-Enter to run, Cmd/Ctrl-/ to comment
That's all we've got! Let's move on to the next tutorial.
If you had any problems with this tutorial, check out the main forum thread here.