0020.Valid Parentheses

Link: 20. Valid Parentheses
Track: NeetCode150

Question

Restate the problem

• Given a string containing only the characters ()[]{}, determine if it is valid.
• A string is valid if every opening bracket is closed by the same type of bracket, and brackets are closed in the correct nested order (the most recent unmatched opening bracket is closed first). Return a boolean.

---

Method	Approach	Time Complexity	Space Complexity
Method 1 ⭐	HashMap + Doubly Linked List	$O(n)$	$O(n)$

Method 1 - Hashmap + stack

Use a stack to track opening brackets; each closing bracket must match the stack top, and the string is valid only if the stack ends empty.

Approach

• Use a stack to store opening brackets and a hashmap that maps each closing bracket to its matching opening bracket.

• Scan the string:

  • if I see an opening bracket, I push it onto the stack.
  • If I see a closing bracket, the stack must not be empty and the top element must match the expected opening bracket from the map; otherwise I return false.

• After the scan, the string is valid only if the stack is empty.

Complexity

• Time Complexity: $O(n)$
• Space Complexity: $O(n)$

Edge Case

• If a closing parenthesis/bracket appears first

Code

class Solution:
    def isValid(self, s: str) -> bool:
        stack = []
 
        dic = {")": "(", "}": "{", "]": "["}
 
        for par in s:
            if par in dic:
                if not stack:
                    return False
 
                op_par = stack.pop()
                if op_par != dic[par]:
                    return False
            else:
                stack.append(par)
        
        return False if stack else True

---

Mistake