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 :)
github : https://github.com/AKHILP96/Data-Structures-and-Algorithms/blob/master/problems/ValidParentheses.js
Top comments (15)
You can check a number is not equal to zero by
if (n) {}
or check empty string byif (!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.
I wrote this way for code readability :)
Yes, that way is better for products. But the boundary between readability and cleaning is not always clear. :)
True that.
Also tried the standard
for
loop approach which actually proved easier to deal with thanevery
:Awesome work man ! keep up !
It’s me again. Here’s my solution.
Test it here: leetcode.com/problems/valid-parent...
As far as I know, the regex will manipulate string and string manipulation is a bit time consuming heavy in javascript.
But smart and concise code though !
It’s true. C/C++ can solve it in almost 0ms.
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 afor...of
loop which works nicely with the empty string case.What do you think?
For :"{[]}" it returns false.
Try solving it here : leetcode.com/problems/valid-parent...
@akhil I updated it to meet that condition!
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;===
, never==
;renturn stack.length === 0
is cleaner.I wrote the implementation below and I find it much cleaner.
Amazing post. I loved the concept.🥳
Just one thing, try moving this from webdev to #algorithms tag for better reach among algo geeks.
My bad, it was meant to be #tutorial.
Thanks a lot for reading :)