Valid Parenthesis
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.
Example 1:
Input: s = "()"
Output: true
Example 2:
Input: s = "()[]{}"
Output: true
Example 3:
Input: s = "(]"
Output: false
Example 4:
Input: s = "([])"
Output: true
Example 5:
Input: s = "([)]"
Output: false
Constraints:
1 <= s.length <= 10^4
s consists of parentheses only '()[]{}'.
My Solution
This can be solved with a stack. We iterate through the characters of the string and if the character is an open parenthesis ( ‘(‘ , ‘[‘ , or ‘{‘) we simply push that character onto the stack. If the character is a closed parenthesis ( ‘)’ , ‘]’ , ‘}’ ) and the stack is empty, we know the string is invalid and we can return false. If the stack is not empty but the character on top of the stack is not the corresponding open parenthesis, we know the string is invalid and can return false. Otherwise we just pop the element on top of the stack. Once we have iterated through all the characters in the string, we finally check whether the stack is empty. If it is, we know the string is valid and can return true. If not, then there are some open parentheses which don’t have a corresponding closed parenthesis so we return false.
Algorithmic time complexity would be O(n), where n is the length of the string. Algorithmic space complexity is O(n) in the worst case for the stack.
class Solution {
public boolean isValid(String s) {
Stack<Character> stack = new Stack<>();
int n = s.length();
for (int i = 0; i < n; i++) {
char c = s.charAt(i);
if (c == '(' || c == '[' || c == '{') {
stack.push(c);
}
else if (stack.empty() || (c == ')' && stack.peek() != '(') ||
(c == ']' && stack.peek() != '[') ||
(c == '}' && stack.peek() != '{')) {
return false;
}
else {
stack.pop();
}
}
return stack.empty();
}
}