Valid Parentheses
Problem Description
Question
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 <= 104
sconsists of parentheses only'()[]{}'.
Solve it on LeetCode
Approaches
1. Using Stack
Intuition:
The problem of validating parentheses can be efficiently solved using a stack data structure as it is ideal for problems involving matched pairs and nested structures. The idea here is to iterate through the characters of the string and use the stack to keep track of opening parentheses. When we encounter a closing parenthesis, we check if it matches the top of the stack. If it does, we can pop the stack; otherwise, the string is invalid.
Steps:
- Initialize a stack to keep track of opening parentheses.
- Loop through each character in the string.
- If a character is an opening bracket ('(', '{', or '['), push it onto the stack.
- If it is a closing bracket, check the stack:
- If the stack is empty, it means there is no matching opening bracket, thus the string is invalid.
- If the stack is not empty, pop the top element from the stack and check if it matches the closing bracket. If not, return false.
- After processing all characters, if the stack is empty, it means all opening brackets had matching closing brackets, so the string is valid. Otherwise, return false.
Code:
Complexity Analysis
- Time Complexity: O(n), where n is the length of the string. We traverse the string once, and each operation on the stack (push/pop) is O(1).
- Space Complexity: O(n) in the worst case, when all characters are opening brackets and are pushed onto the stack.