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.
Every close bracket has a corresponding open bracket of the same type.
Link: https://leetcode.com/problems/valid-parentheses/
Problem Explanation with examples:-
Example 1
Input: s = "()"
Output: true
Example 2
Input: s = "()[]{}"
Output: true
Example 3
Input: s = "(]"
Output: false
Constraints
1 <= s.length <= 10<sup>4</sup>sconsists of parentheses only'()[]{}'.
Intuition:-
A stack is suitable for such problems where we need to keep track of the last element.
Keep pushing the opening brackets into the stack.
If we encounter a closing bracket, we check if the last element in the stack is the corresponding opening bracket. If it is, we pop the last element from the stack. If it is not, we return False.
If the stack is empty at the end, we return True. Else, we return False.
Solution:-
Create a stack.
Iterate through the string.
If the current character is an opening bracket, we push it into the stack.
If the current character is a closing bracket, we check if the last element in the stack is a corresponding opening bracket. If it is, we pop the last element from the stack. If it is not or if the stack is empty, we return False.
If the stack is empty at the end, we return True. Else, we return False.
Code:-
JAVA Solution
class Solution {
public boolean isValid(String s) {
Stack<Character> st = new Stack<>();
for(int i=0;i<s.length();i++){
char c = s.charAt(i);
if(c == '(' || c == '{' || c == '[')
st.push(c);
else{
if(c == ')'){
if(st.empty() || st.pop() != '(')
return false;
}
if(c == '}'){
if(st.empty() || st.pop() != '{')
return false;
}
if(c == ']'){
if(st.empty() || st.pop() != '[')
return false;
}
}
}
return st.empty();
}
}
Python Solution
class Solution:
def isValid(self, s: str) -> bool:
stack = []
for i in s:
if i == '(' or i == '{' or i == '[':
stack.append(i)
else:
if i == ')':
if len(stack) == 0 or stack.pop() != '(':
return False
if i == '}':
if len(stack) == 0 or stack.pop() != '{':
return False
if i == ']':
if len(stack) == 0 or stack.pop() != '[':
return False
if len(stack) == 0:
return True
else:
return False
Complexity Analysis:-
TIME:-
The time complexity is O(n) where n is the length of the string. We iterate through the string once.
SPACE:-
The space complexity is O(n) where n is the length of the string. We use a stack to keep track of the opening brackets.