Valid Parentheses (LeetCode #20)

Note: This problem is on the Grind 75 list.

Question:

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.
3. Every close bracket has a corresponding open bracket of the same type.

Example 1:

Input: s = "()"
Output: true

Example 2:

Input: s = "()[]{}"
Output: true

Example 3:

Input: s = "(]"
Output: false

Solving data structure and algorithm problems can be hard and frustrating. It is easy to get stuck on even the “Easy” problems when you are just starting out. If this is you, I hope to be able to help walk you through the “Valid Parentheses” problem to help you build the intuition for solving it.

Approach:

With these problems, we really want to understand what they are asking us. With this problem, we want to make sure that our brackets are opening and closing of the same type in the right order. This does not mean they have to sit next to each other in theory* (check out the example below). A good way to understand this is to look at the examples.

Example 2 illustrates this very well

()[]{}

We could also have the following*:

({[]})

This would be perfectly valid depending on our algorithm.

I like to think about it like this: When I come across an opening bracket like “(“, I need to keep track (create a history) of the bracket that would close it and that bracket’s location. Eventually, if I come across a closing bracket, I need to be able to find out if a previously stored bracket (taken from that history) corresponds with the closing bracket. This will tell me that the brackets are of the same type and in the right order.

Let’s look at an example. Let’s say we have the following:

({[]})

As we start iterating over these brackets, we will start like this:

(
history:
example: ({[]})

We look at the “(“. Now we think to ourselves, “Which bracket would close this?” We add a “)” to our history because we know that it would close that.

(
history: ), 
example: ({[]})

Then, we move onto “{“ and repeat the process.

({
history: ), }
example: ({[]})

Notice how we now have a “}” in our history as we know it closes “{“. Let’s keep going.

({[
history: ), }, ]
example: ({[]})

We continue this process until we reach a closing bracket. When we reach a closing bracket (it does not matter which type), that is when we finally check our history.

({[]
history: ), }, ]
example: ({[]})

Now we have come across an “]” which is a closing bracket. At this point, we now want to know if there was an opening bracket (“[“ in this case) at a previous point in our history that aligns with this closing bracket. We can figure this out by checking our history and seeing what was last in it. When looking at our history, we are going to check the last item that was put in first. Think about it like we are retracing our steps to see what previously happened.

We know that in our history we have kept a log of which brackets were needed to close the previous opening brackets. Therefore, if we see a closing bracket, we can imagine which bracket would be the opening one. We can then compare the closing bracket in our history with the bracket we are currently looking at to see if they are the same. This means that we have found a pair of brackets.

So let’s look at it like this: We are currently looking at “]”. We now check our history to see what the previous bracket was (a closing bracket that corresponds with an opening bracket). In this case, the previous bracket was “]” (opening: “[“) which means that we have now found a pair of brackets of the same type and are in the right order.

({[]
history: ), }, ] <- The opening bracket is "[" which put this here
example: ({[]})

We now remove the bracket from our history as we have confirmed that it matches another bracket and is in the right order. We are only keeping track of which brackets have not been closed yet. Afterward, we move on to the next bracket.

({[]}
history: ), }
example: ({[]})

Hey! We came across another closing bracket. Let’s repeat the process and check our history.

({[]}
history: ), }
example: ({[]})

Does the closing bracket correspond with the closing bracket in our history? Yes! We now have another match! Remember: Once we have found a match, let’s remove the bracket from our history.

({[]}
history: )
example: ({[]})

Now we move on:

({[]})
history: )
example: ({[]})

We are on our final bracket and it is a closing one. Does it match the closing bracket in our history? YES!

({[]})
history: )
example: ({[]})

We can remove the bracket from our history and now we are done! We can now officially confirm that all our opened brackets have been “closed.”

({[]})
history: 
example: ({[]})

If we understand the intuition behind the problem, it makes it much easier to come up with a solution and it starts to click more in our brains.

Now when we come up with the code (or solution), we may consider the following: “How can I keep a history?”, “How do I check to see if an opening bracket corresponds with a closing one?”, “What happens if we check the history after finding a closing bracket and the closing bracket in the history does not match ours?”

These are all valid questions along with others. We should consider the things we already know about the programming language we are using, the original problem and what it is asking for, and our knowledge of data structures that we could use.

I am going to use JavaScript for my solution. It is as follows:

const isValid = (s) => {
  let brackets = {
    "(": ")",
    "[": "]",
    "{": "}",
  };
let stack = [];
for (let char of s) {
    if (brackets[char]) {
      stack.push(brackets[char]);
    } else {
      if (stack.pop() !== char) return false;
    }
  }
  return !stack.length;
};

So a few things:

1. I am using an array called stack to act as a Stack in JavaScript. Stacks follow the LIFO method (Last in, First out) which means they are perfect for our history.
2. I used a JavaScript Object brackets like a Hashmap/Dictionary to store the opening brackets and their corresponding closing brackets.

A quick walkthrough of the code:

I set up the variables brackets and stack to represent a “dictionary” for looking up the opening brackets/closing brackets and a history to keep track of the brackets we’ve seen (or what we are looking for the close them and in the order) respectively.

From there, I set up a for loop to walk through each bracket. This conditional below may look a little tricky, but it is actually not. It is essentially saying “if the character were looking at is an opening bracket in our hashmap, put its corresponding closing bracket into the stack/history” ELSE “if the character is not an opening bracket but a closing one, get the last bracket from our stack/history and check to see if it corresponds with the current closing bracket we are checking. If not, return false meaning that the brackets are not in order”

if (brackets[char]) {
    stack.push(brackets[char]);
  } else {
    if (stack.pop() !== char) return false;
}

Finally, the return statement is simply a sanity check to make sure our stack is empty which means that we have checked everything and we are saying that the parentheses are valid.

return !stack.length;

In closing:

The final bit that I would add is to always make sure that you check the question to see if it mentions any edge cases. I added the final code below with a couple of checks for edge cases. One checks to see if the length of the string is not odd (even) because we won’t have all the brackets corresponding. The second one says that an empty string is valid.

const isValid = (s) => {
  if (s.length % 2 !== 0) return false;
  if (s.length === 0) return true;
  let brackets = {
      "(": ")",
      "[": "]",
      "{": "}",
  };
  let stack = [];
  for (let c of s) {
      if (brackets[c]) {
        stack.push(brackets[c]);
      } else {
        let val = stack.pop();
        if (stack.pop !== c) return false;
      }
  }
  return !stack.length;
};

I hope you found this helpful!