Valid Parentheses Solution for Google
Company: Google · Difficulty: Medium · Topics: Stack, String
Problem Statement
Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.
An input string is valid if:
1. Open brackets must be closed by the same type of brackets.
2. Open brackets must be closed in the correct order.
3. Every close bracket has a corresponding open bracket of the same type.
Examples
Example 1:
Input: s = "()"
Output: true
Explanation: Simple valid parentheses.
Example 2:
Input: s = "()[]{}"
Output: true
Explanation: Valid parentheses with different types.
Example 3:
Input: s = "(]"
Output: false
Explanation: Invalid - closing bracket doesn't match opening bracket.
Example 4:
Input: s = "([)]"
Output: false
Explanation: Invalid - brackets are not closed in correct order.
Intuition
The key insight is that we need to use a stack to keep track of opening brackets. When we encounter a closing bracket, we check if it matches the most recent opening bracket (top of stack). If it matches, we pop the opening bracket; if not, the string is invalid.
Approach
1. Use a stack to store opening brackets
2. For each character in the string:
- If it's an opening bracket, push it onto the stack
- If it's a closing bracket, check if it matches the top of the stack
- If it matches, pop the top element; if not, return false
3. At the end, check if the stack is empty (all brackets are properly closed)
Solution
⚠️ Disclaimer: Don't jump directly to the solution, try it out yourself first. Only look at the solution after you've given it a good attempt.
Solution: Stack Approach
Time Complexity: O(n) - Single pass through the string
Space Complexity: O(n) - Stack can grow up to n elements