LeetCode Discussion: validParentheses

Take a look at this LeetCode problem statement:

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.
An input string is valid if:
1.  Open brackets must be closed by the same type of brackets.
2.  Open brackets must be closed in the correct order.

The first thing we should always do when attacking a DSA question is decide which data structure would best solve the problem. In this case, we’re going to use a stack and a hash map. To approach this problem, we will create a map of parentheses with opening parentheses as keys and corresponding closing ones as the value. For the stack, we’ll declare an empty array and check the string character by character. So first, let’s create our key-value pairs:

const obj = {
    "(": ")",
    "{": "}",
    "[": "]",
  }

And then let’s initialize our array:

const stack = [];

Now, let’s create a for loop where we loop over all the characters of the string, or in other words, all of the brackets. Next, we check if the character is an opening bracket. If yes, we’ll push it to the stack. If it’s a closing bracket, we have to check for the last entry in the stack. Moving forward, if the last entry in the stack is the opening bracket of the current closing bracket, then we can push it to the stack. If not, we return false because the brackets are not balanced.

for (const paran of s) {
    if (obj.hasOwnProperty(paran)) {
      stack.push(paran)
    } else {
      const closeParan = stack.pop();
      if (paran !== obj[closeParan]) {
        return false;
      }
    }
  }

Lastly, if the stack is not empty, that is due to an opening bracket not having a corresponding closing bracket. So, depending on the stack length we will return either false or true. In total, our code will look like this:

var isValid = function (s) {

  const obj = {
    "(": ")",
    "{": "}",
    "[": "]",
  }

  const stack = [];

  for (const paran of s) {
    if (obj.hasOwnProperty(paran)) {
      stack.push(paran)
    } else {
      const closeParan = stack.pop();
      if (paran !== obj[closeParan]) {
        return false;
      }
    }
  }

  return stack.length === 0;
};

Happy Coding! =)