Valid Parentheses | Leetcode #20 | Easy

In this post I will discuss the solution to the leetcode problem — Valid Parentheses.

Problem:

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.

Example 1:

Input: s = "()"
Output: true

Example 2:

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

Example 3:

Input: s = "(]"
Output: false

Example 4:

Input: s = "([)]"
Output: false

Example 5:

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

Constraints:

• 1 <= s.length <= 104
• s consists of parentheses only '()[]{}'.

Solution:

As mentioned in the problem statement, parentheses, braces and brackets (I will just call them brackets in the text below) should be closed by the same type. i.e '(' needs to be closed by')' . This seems to be a pair of characters that work together. Let’s use this concept to build the algorithm to solve this problem.

1. Create a map called charMap which stores the opening and it’s corresponding closing character.
2. The best suitable data structure for this use case is Stack because of it’s Last-In-First-Out(LIFO) nature i.e. last inserted element will be taken out first. So, let’s create a variable stack of type Character.
3. For each character in the input string follow the steps from #4 to #6
4. If the charMap contains a key with the character, that means it is one of the opening brackets and hence we push it to the stack.
5. Else, it is one of the closing brackets. Now, (a) get the top element from the stack using pop()method (b) get the value for that element from the charMap (c) compare it with the current character in the iteration. If they don’t match, it means they are not the matching brackets and hence we return false.
6. There is another corner case where the closing bracket is the last character in the string after all the matching brackets or closing bracket is the only character in the input string. In this case we need to add another or condition to the if block in step #5 to check is stack is empty.
7. In the end if the stack is empty, we have all the brackets matching and hence we return true. Otherwise return false.

This is how the code looks like —

class Solution {
  private static final Map<Character, Character> charMap = new HashMap<>();
static {
  charMap.put('(', ')');
  charMap.put('[', ']');
  charMap.put('{', '}');
}
public boolean isValid(String s) {
  Stack<Character> stack = new Stack<>();
  for (char ch : s.toCharArray()) {
    if (charMap.containsKey(ch)) {
      stack.push(ch);
    } else {
        if (stack.empty() || ch != charMap.get(stack.pop())) {
          return false;
        }
      }
    }
    return stack.empty();
  }
}

Hope this helps! Happy coding! 🙂

If you think the solution can be improved or misses something, feel free to comment. There is always some room for improvement.

Find the solutions to the leetcode problems here — https://github.com/rishikeshdhokare/leetcode-problems