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

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:

1. Here is the step-by-step approach of the algorithm:

1. Initialize an empty stack.

2. Traverse the input string character by character.

3. If the current character is an opening bracket (i.e., ‘(‘, ‘{‘, ‘[‘), push it onto the stack.

4. 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.

5. Otherwise, pop the top element from the stack and check if it matches the current closing bracket.

6. If it does not match, return false, because the brackets are not valid.

7. 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.

8. 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.

Related Banners

Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription

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