Valid Parentheses Leetcode Solution
Valid Parentheses Leetcode 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.
- Every close bracket has a corresponding open bracket of the same type.
Valid Parentheses Leetcode Problem Solution :
Constraints :
- 1 <= s.length <= 104
- s consists of parentheses only ‘( )[ ]{ }‘.
Example 1:
Input: s = “()[]{}”
Output: true
Example 2:
Input: s = “(]”
Output: false
Idea:
The problem requires us to determine if the given string of brackets is valid or not.
We can use a stack data structure to keep track of opening brackets encountered and check if they match with the corresponding closing brackets.
Approach:
Here is the step-by-step approach of the algorithm:
Initialize an empty stack.
Traverse the input string character by character.
If the current character is an opening bracket (i.e., ‘(‘, ‘{‘, ‘[‘), push it onto the stack.
If the current character is a closing bracket (i.e., ‘)’, ‘}’, ‘]’), check if the stack is empty. If it is empty, return false, because the closing bracket does not have a corresponding opening bracket.
Otherwise, pop the top element from the stack and check if it matches the current closing bracket.
If it does not match, return false, because the brackets are not valid.
After traversing the entire input string, if the stack is empty, return true, because all opening brackets have been matched with their corresponding closing brackets.
Otherwise, return false, because some opening brackets have not been matched with their corresponding closing brackets.
Complexity:
Time complexity:
The time complexity of the solution is O(n), where n is the length of the input string.
This is because we traverse the string once and perform constant time operations for each character.Space complexity:
The space complexity of the solution is O(n), where n is the length of the input string.
This is because the worst-case scenario is when all opening brackets are present in the string and the stack will have to store them all.
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
Code :
class Solution {
public:
bool isValid(string s) {
stack< char> st;
for (char c : s) {
if (c == '(' || c == '{' || c == '[') {
st.push(c);
} else {
if (st.empty() || (c == ')' && st.top() != '(') ||
(c == '}' && st.top() != '{') ||
(c == ']' && st.top() != '[')) {
return false;
}
st.pop();
}
}
return st.empty();
}
};
class Solution {
public boolean isValid(String s) {
Stack< Character> stack = new Stack();
for (char c : s.toCharArray()) {
if (c == '(' || c == '[' || c == '{') {
stack.push(c);
} else {
if (stack.isEmpty()) {
return false;
}
char top = stack.peek();
if ((c == ')' && top == '(') || (c == ']' && top == '[') || (c == '}' && top == '{')) {
stack.pop();
} else {
return false;
}
}
}
return stack.isEmpty();
}
}
class Solution(object):
def isValid(self, s):
stack = []
for c in s:
if c in '([{':
stack.append(c)
else:
if not stack or \
(c == ')' and stack[-1] != '(') or \
(c == '}' and stack[-1] != '{') or \
(c == ']' and stack[-1] != '['):
return False
stack.pop()
return not stack
Get over 200+ course One Subscription
Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others
Login/Signup to comment