Valid Parentheses

The solution to the Valid Parentheses problem in LeetCode using Java

Jan 23, 20235 min read

Overview:

Valid Parentheses is an easy-level problem taken directly from LeetCode. It is a string problem that tests your basic data structures knowledge. In this article, we will discuss how to identify the correct data structure to use to solve the problem.

Question:

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

For example, if s = "{[]}()", the string is valid because each open bracket is closed by the same type of bracket.

If s = "{[)}()", the string is not valid because ) does not have a corresponding opening bracket.

Brain Storm:

According to the question, we know that there are only 3 types of brackets: (), {}, and []. However, we can further categorize the brackets as opening or closing brackets.

If we go through each character in the string in order, we can see that as soon as we find a closing bracket, the bracket we visited right before it determines if the parentheses are valid or not. What that means is that if the current character curr is a closing bracket, then the previously visited character prev should be an opening bracket and should be of the same type as curr for the pair of characters to be valid.

If we find a closing character prev that is not of the same type as curr, then we can say that the pair is invalid. Transversely, if we find one invalid pair, we can conclude that the entire string has invalid parentheses.

On the other hand, to show that a string has valid parentheses, we need to show that each pair of brackets is valid. When we find a valid pair, however, we need to forget about the two characters and move on with our iteration to check whether the next pair is valid. Therefore, we can remove both prev and curr and move on to the next character in the string.

Since we are deleting valid pairs from the string, if the string is empty after we have iterated through every character in it, we can conclude that the string has valid parentheses.

Data Structure Selection:

One problem we haven’t solved so far is how to access the previous character to check if it makes a valid pair with the current character. Since we need to find a valid pair for each opening and closing bracket, what we can do is save each opening bracket in a data structure in the order that it was visited. Then once we find a closing bracket, we can check to see if the last added character in the data structure makes a valid pair with the current character. This lets us not interrupt the flow of the iteration and helps us maintain the logic we discussed while brainstorming above.

If we do find a valid pair, instead of deleting both characters from the string, we can only delete the last added character from the data structure and move on with the iteration. If the next character in the string is a closing bracket, then it should be compared with the next last added character we can find in the data structure after we have deleted the original last added character.

Storing data in order of traversal and accessing and deleting the last added data means that we need to use a data structure that follows the Last In First Out (LIFO) principle. The most common data structure that follows LIFO is the Stack.

Stack:

Stack is a linear data structure that follows the LIFO principle. A LIFO data structure lets us access (read, update, or delete) the last added item in constant runtime. In a Stack, we can access the last added item from the top or the front of the data structure.

When we come across an opening bracket in our string iteration, we will add or push it to the top of the stack. When we come across a closing bracket, however, we will compare it with the opening bracket at the top of the stack. This lets us compare each closing bracket with its corresponding opening bracket in the order that was given to us in the string.

In the above visualization, as soon as we find an invalid pair, we can conclude that the entire string is invalid. This is the same conclusion we came up with during the brainstorming process. For the entire string to be valid, however, we need each and every pair of brackets to be valid.

If the pair of current brackets are valid, then we can remove or pop the opening bracket from the stack so we can access the next opening bracket to compare with the next closing bracket.

Since we are adding and deleting characters from the stack, if the stack is empty at the end of the string iteration, we can conclude that the string is valid.

Solution:

For the solution, we can simply iterate over each character in the string. If the character is a closing bracket, we will compare it with the character at the top of the stack to check if the pair is valid. If the pair is invalid, we can simply return false and end the program. If the pair is valid, then we can pop the character from the top of the stack and move on with our iteration. If we reach the end of the string and the stack is empty, we can conclude that the string is valid.

class Solution {
  public boolean isValid(String s) {
    Stack<Character> stack = new Stack<Character>();
    for (int i = 0; i < s.length(); i++) {
      char c = s.charAt(i);
      if (c == ')') {
        if (!stack.empty() && stack.peek() == '(') {
          stack.pop();
        } else {
          return false;
        }
      } else if (c == '}') {
        if (!stack.empty() && stack.peek() == '{') {
          stack.pop();
        } else {
          return false;
        }
      } else if (c == ']') {
        if (!stack.empty() && stack.peek() == '[') {
          stack.pop();
        } else {
          return false;
        }
      } else {
        stack.push(c);
      }
    }
    if (stack.empty()) {
      return true;
    } else {
      return false;
    }
  }
}

In our code above, we are also checking to see if the stack is empty or not before trying to access the character at the top because Java will throw an EmptyStackException if we try to access data in an empty stack.

The code has a runtime complexity of O(n) because in the worst case, the program will loop through each character in the string at least once.

In a nutshell:

The Valid Parentheses problem is an easy-level problem from LeetCode and is one of the first questions companies may throw at you during your interview. After investigating what we need to do to get the solution, we found out that we need to use a data structure that follows the LIFO principle. We used a Stack to solve this problem but there are other data structures available in Java like LinkedList or Deque with which you can get similar results. There are also a lot more ways to improve the overall runtime of the program which you can explore and apply.

Happy Coding!