Practice/Google/Leetcode 20. Valid Parentheses

Leetcode 20. Valid Parentheses

CodingMust

Problem

Given a string containing only the characters (, ), {, }, [, and ], determine if the input string represents a valid bracket sequence.

A string is considered valid if:

• Every opening bracket has a corresponding closing bracket of the same type
• Opening brackets are closed in the correct order
• Each closing bracket matches the most recently opened unmatched opening bracket

Requirements

1. Return true if the string is valid, false otherwise
2. Handle all three types of brackets: parentheses (), square brackets [], and curly braces \{\}
3. Properly validate nested bracket structures
4. Account for empty strings (which should return true)

Constraints

• 0 <= s.length <= 10^4
• The string consists only of the characters: (, ), {, }, [, ]
• Expected time complexity: O(n)
• Expected space complexity: O(n)

Examples

Example 1:

Input: s = "()" Output: true Explanation: A single pair of parentheses is valid.

Example 2:

Input: s = "()[]{}" Output: true Explanation: Multiple bracket pairs in sequence, all properly matched.

Example 3:

Input: s = "(]" Output: false Explanation: The opening parenthesis is incorrectly matched with a closing square bracket.

Example 4:

Input: s = "{[]}" Output: true Explanation: Square brackets are properly nested within curly braces.

Example 5:

Input: s = "([)]" Output: false Explanation: The brackets are interleaved incorrectly. The opening square bracket is inside the parentheses but its closing bracket is outside.