Back to course home
0% completed
Vote For New Content
Solution: Valid Parentheses
Problem Statement
Determine if an input string containing only the characters '(', ')', '{', '}', '[', and ']' is valid. A string is considered valid if:
- Open brackets must be closed by the same type of brackets.
- Open brackets must be closed in the correct order.
- Each close bracket has a corresponding open bracket of the same type.
Examples
-
- Input:
"(]"
- Expected Output:
false
- Justification: The opening parenthesis '(' is not closed by its corresponding closing parenthesis.
- Input:
-
- Input:
"{[]}"
- Expected Output:
true
- Justification: The string contains pairs of opening and closing brackets in the correct order.
- Input:
-
- Input:
"[{]}"
- Expected Output:
false
- Justification: The opening square bracket '[' is closed by a curly brace '}', which is incorrect.
- Input:
Constraints:
- 1 <= s.length <= 10<sup>4</sup>
s
consists of parentheses only '()[]{}'.
Solution
- Initialization:
- Start with an empty stack.
- For every bracket in the input string:
- If the bracket is an opening bracket ('(', '{', '['), push it onto the stack.
- If the bracket is a closing bracket (')', '}', ']'):
- If the stack is empty, return false.
- Pop the top of the stack and check if it matches the corresponding opening bracket.
- Validation:
- If the current closing bracket doesn't match the top of the stack, return false.
- If the stack is not empty after processing all brackets in the string, return false.
- Final Output:
- If the stack is empty at the end, return true, indicating that the string has valid parentheses.
Algorithm Walkthrough
Using the input "{[]}"
:
- Start with an empty stack.
- Encounter '{', push onto the stack.
- Encounter '[', push onto the stack.
- Encounter ']', pop from the stack and check if the popped character is '['. It matches, so continue.
- Encounter '}', pop from the stack and check if the popped character is '{'. It matches.
- The string is processed and the stack is empty, so return true.
Code
Python3
Python3
. . . .
Complexity Analysis
- Time Complexity: O(n) where n is the length of the string. Each character is processed once.
- Space Complexity: O(n) in the worst case when all characters are opening brackets.
.....
.....
.....
Like the course? Get enrolled and start learning!
Table of Contents
Contents are not accessible
Contents are not accessible
Contents are not accessible
Contents are not accessible
Contents are not accessible