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:
- Open brackets must be closed by the same type of brackets.
- 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.
- Create a map called
charMap
which stores the opening and it’s corresponding closing character. - 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 variablestack
of type Character. - For each character in the input string follow the steps from #4 to #6
- If the
charMap
contains a key with the character, that means it is one of the opening brackets and hence we push it to thestack
. - Else, it is one of the closing brackets. Now, (a) get the top element from the
stack
usingpop()
method (b) get the value for that element from thecharMap
(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. - 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. - 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