This is our solution and implementation to problem #20: Valid Parentheses on LeetCode.
Our code is written in Java. If you want to code your solution in a different language, no worries, as the core concepts will carry over from language to language. This page includes our analysis of the problem, our implementation strategy a breakdown on the space and time complexity, and the full code implementation.
If you would like to view the original problem and solve it, please visit: Valid Parentheses on LeetCode.
Problem Analysis
We need to validate that the three types of parenthesis open and close correctly. The constraints are:
- Counts of openers and closers must be consistent for all chars
- Inner pairs must be closed before outer pairs are closed
Therefore, we cannot simply keep track of the counts of openings and closings, we must keep track of the order of chars as well.
Implementation Strategy
We'll use a stack to record each opening parenthesis we encounter. Then, whenever we encounter a closing parenthesis, we'll check the stack to see if it matches the expected opening parenthesis. If it does, we'll pop the stack and repeat the process. This also covers nested parenthesis correctly, such as [[()]]
. At the end, we'll check that the stack is emtpy, and if it is, we return that the string is valid.
Space and Time Complexity
The time complexity is O(n), as we iterate over the string exactly once and since stack operations are constant time. The space complexity is O(n) as the size of the stack is proportional to the size of the input string.
Additional Resources
Full Code
Our solution is given in the Java code below:
All of our solutions are hosted on GitHub. The code on this page was pulled from the repo.