DEV Community is a community of 787,570 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

Valid parentheses, solving a Facebook interview question.

This is one of the most commonly asked screeing questions, Especially if the interview is conducted by Hackerrank, there's a good chance that they will ask this question. I was asked this exact same question 4 times by Hackerrank.

Question : Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:
Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.
An empty string is considered valid.

Eg:

string = "()[]{}"              //valid
string = "[{()]}"              //invalid
string = ""                    //valid

Let's solve this,

At its bare minimum, the question is asking us to find matching opening and closing parentheses. So for :
"(", ")" is the valid closing parentheses
"{", "}" is the valid closing parentheses
"[", "]" is the valid closing parentheses

Or in other words, we can say that the "pairs" cancel out each other, from this we can say that the order matters.

A good data structure that will help us with :
1 > Storing the parentheses and cancel them when the match is found,
2 > Keeping track of parentheses

is Stack. We shall push the opening parentheses on to the stack and pop it when we encounter a closing parenthesis, and that the same time we can check if the closing parenthesis is the valid match for the parentheses being popped.

Implementation - 1

Here we can make a small optimization of checking if the length is even if it's not then obviously the string is not valid.
Converting the above idea into code :

var isValid = function(S) {
let stack = [];
if(S == '') return true;
if(S%2 != 0) return false;
for(let s of S){
if(s == '(' || s == '{' || s == '['){
stack.push(s);
}else{
if(stack.length == 0) return false;
let c = stack.pop();
if(c == '(' && s != ')'){
return false;
}
if(c == '{' && s != '}'){
return false;
}
if(c == '[' && s != ']'){
return false;
}
}
}

if(stack.length != 0) return false;      // for conditions like "{([])}}}"
return true;
};

Now this works well, but can we do better? There are a lot of if-else conditions just for checking the "pairs". Let's try to make it more concise.

Implementation - 2

Since the main work of the if conditions are to match the parentheses, we use another data structure, the Hashmaps.

Since a closing parenthesis must match with a corresponding opening parenthesis, we create a mapping between closing and opening parenthesis. So the algorithm works this way :
1 > Check if the current symbol is in the hashmap, if not the push it on the stack.
2 > If the current symbol is in the hashmap, then pop from the stack and compare it with the value corresponding to hashmap entry.

So if the top of the current symbol is ")" then we pop from the stack, compare the popped value with the value corresponding to ")" in hashmap which is "(", if they arent same then the string is not valid.

The code will make it a lot clear.

var isValid = function(S) {

if(S == '') return true;
if(S.length%2 != 0) return false;

let map = {};
map[")"] = "(";
map["}"] = "{";
map["]"] = "[";

console.log(map);

let stack = [];
for(let s of S){
if(!map[s]){
stack.push(s);
}else{
if(stack.length == 0) return false;
let c = stack.pop();
if(c != map[s]) return false;
}
}

if(stack.length !=0) return false;
return true;
};

I hope you liked my explanation if you know a better way of solving this problem then please share it with us :)

Discussion (15) Nam Hoang Le • Edited on

You can check a number is not equal to zero by if (n) {} or check empty string by if (!s) ....
Of course, just use object literal for you map. :)

The last statement should be return !stack.length.

Bonus point: we can solve it shorter by using recursion and String replace method. JS Bits with Bill

Also tried the standard for loop approach which actually proved easier to deal with than every:

const isValid = function(s) {

const pairs = {
'(': ')',
'[': ']',
'{': '}'
};

const openParens = [];
for (let i = 0; i < s.length; i++) {
const endParen = pairs[s[i]];

if (endParen) openParens.push(endParen);
else if (openParens[openParens.length - 1] === s[i]) openParens.pop();
else return false;
}

return openParens.length ? false : true;
}; Nam Hoang Le

It’s me again. Here’s my solution.

function isValid(s) {
const t = s.replace(/\(\)|\[\]|\{\}/g, "");
return s == t ? !s : isValid(t);
}; JS Bits with Bill • Edited on

I gave this a shot! Similar to yours, my approach was to split the string and track the expected closing parens in a separate array. I used the every method instead of a for...of loop which works nicely with the empty string case.

const isValid = function(str) {

const pairs = {
'(': ')',
'[': ']',
'{': '}'
};

const closingParens = [];
return [...str].every(validate);

function validate(char, i, arr) {
const isLastChar = i === arr.length - 1;

// If char found in pairs, push closing paren to arr
if (pairs[char] && !isLastChar) {
closingParens.push(pairs[char]);
return true;

} else {
// If char has no closing paren, return false
if (!closingParens.length) return false;

// Check if current char is last in arr
const lastCharInArray = closingParens.pop();

// If last char and unmatched parens, return false
if (isLastChar && closingParens.length) return false;

// If pair found, continue
if (char === lastCharInArray) return true;
}
}
};

What do you think? I conduct interviews (not at Facebook), I don't ask questions about algorithms, but I wouldn't probably hire someone who writes code like that, especially if it's a mid-senior position, because there are too many bad practices:

• var shouldn't be used anymore;
• variables should have more descriptive names and start with a lowercase character;
• always ===, never ==;
• static constants should be defined outside functions;
• renturn stack.length === 0 is cleaner.

I wrote the implementation below and I find it much cleaner.

const CLOSING_BRACKET_BY_MATCH = {
'(': ')',
'[': ']',
'{': '}',
};

const testBrackets = (input) => {
const stack = [];
let len = 0;

if (input.length % 2 !== 0) {
return false;
}

for (const character of input) {
if ('([{'.indexOf(character) !== -1) {
stack.push(character);
len += 1;
} else {
const lastCharacterPushed = stack[len - 1];

if (len === 0 || (CLOSING_BRACKET_BY_MATCH[lastCharacterPushed] !== character)) {
return false;
}

stack.pop();
len -= 1;
}
}

return len === 0;
}; mayank joshi

Amazing post. I loved the concept.🥳

Just one thing, try moving this from webdev to #algorithms tag for better reach among algo geeks.