Optimal Stack-Based Approach & Code:
- Use a Last-In-First-Out (LIFO) stack to match closing brackets with the most recently opened bracket.
def is_valid_parentheses(s: str) -> bool:
stack = []
bracket_map = {')': '(', '}': '{', ']': '['}
for char in s:
if char in bracket_map:
top = stack.pop() if stack else '#'
if bracket_map[char] != top:
return False
else:
stack.append(char)
return len(stack) == 0
Complexity & Key Logic:
- Time Complexity: O(N) scanning the string of length N once.
- Space Complexity: O(N) worst-case stack space when all characters are opening brackets.
- Algorithm Details:
- Opening brackets are pushed onto the stack.
- When encountering a closing bracket, verify that the stack is non-empty and that the popped opening bracket matches the expected pair.
- After processing the entire string, the stack must be completely empty for the string to be valid.