Hello coders! Today we will be discussing the solution to theĀ Valid Parentheses LeetCode Problem.
Problem Statement
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
Constraints:
1 <= s.length <= 104sconsists of parentheses only'()[]{}'
Analysis
The question is asking us to determine if the given string is a valid set of parentheses. A set of parentheses is valid if each opening parentheses has a corresponding closing parentheses. The tricky part here is that the parentheses can be nested, like "(())". If we think about what is happening with the input "(())", we are really stacking the opening parentheses until we reach a closing parentheses. Once we reach the closing parentheses, if it matches the last seen opening parentheses, we can discard that pair of parentheses and continue. We can say a closing parentheses matches an opening parentheses if it is the correct character. For example ')' matches '(', but does not match '{'.
A stack, as you might've guessed, is the appropriate data structure to solve this problem. If we come across an open parentheses, we push the parentheses onto the stack and continue. If we come across a closing parentheses, we check to see if it matches the parentheses on the top of the stack. If it does, we can discard, or pop, the opening parentheses on the top of the stack and continue until we reach the end of the input string.
Implementation
1import java.util.Stack;
2
3public class ValidParentheses {
4
5 public boolean isValid(String s) {
6 if (s == null || s.length() == 0) {
7 return false;
8 }
9 Stack<Character> stack = new Stack<>();
10 for (int i = 0; i < s.length(); i++) {
11 Character currentChar = s.charAt(i);
12 if (currentChar == '(' || currentChar == '{' || currentChar == '[') {
13 stack.push(currentChar);
14 }
15 else {
16 if (stack.isEmpty() || !isMatch(stack.pop(), currentChar)) {
17 return false;
18 }
19 }
20 }
21 return stack.isEmpty();
22 }
23
24 private boolean isMatch(Character open, Character close) {
25 return (open == '(' && close == ')') || (open == '[' && close == ']') || (open == '{' && close == '}');
26 }
27
28}
Before we move on to the space and time complexity of this algorithm, there are a couple of edge cases we caught in the implementation above. First, on line 16, we are first checking if the stack is empty before seeing if the closing parentheses we are currently at matches the parentheses on the top of the stack. If we don't check if the stack is empty, there is a possibility of calling stack.pop() on an empty stack, which will throw an EmptyStackException. We would run into this scenario with the input ")(".
Additionally, on line 21, if the stack is not empty after we have iterated through the entire input string, we return false. This is checking to make sure there aren't extra opening parentheses that don't have a corresponding closing parentheses, like with the input "([]".
Time Complexity
We are, in the worst case, iterating over each character in the input string once. Given that the length of the input string is represented as n, we can say the time complexity of the algorithm is O(n).
Space Complexity
We are using an auxiliary data structure, the stack, to store our opening parentheses. In the worst case scenario, we could store up to n characters. This could happen if the input is all opening parentheses, like "([{(([{". Therefore, the space complexity of the algorithm is O(n).
Conclusion
The Valid Parentheses LeetCode problem can be solved in O(n) time and O(n) space. At the current time of writing, this solution is 99.43% faster than all Java submissions, and uses less memory than 75.68% of all Java submissions!
The code can be found on my github - if you found it helpful, please leave the repo a star!