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 :)

github : https://github.com/AKHILP96/Data-Structures-and-Algorithms/blob/master/problems/ValidParentheses.js