Leetcode 20: Valid Parentheses

 

1. Problem Statement (Simple Explanation):

You're given a string s containing only these characters:

• '(' , ')' , '{' , '}' , '[' , ']'

You must determine if s is a valid parentheses string.

A string is valid if:

1. Every opening bracket has a matching closing bracket of the same type.

2. Brackets are closed in the correct order (properly nested).

3. No extra closing brackets appear without a matching opening bracket.

Return true if valid, otherwise false.

2. Examples:

Example 1:

Input: s = "()"

Output: true

Example 2:

Input: s = "()[]{}"

Output: true
Explanation: "()", "[]", and "{}" are all valid and appear in correct order.

Example 3:

Input: s = "(]"

Output: false
Explanation: ( must be closed by ), not ].

Example 4:

Input: s = "([])"

Output: true
Explanation: Proper nesting: "(" + "[]" + ")".

Example 5:

Input: s = "([)]"

Output: false
Explanation: Order is wrong; '(' is closed after ']', not after ')'.

3. Approach – Stack (Standard Solution):

This is a classic stack problem.

Intuition:

• Whenever we see an opening bracket ((, {, [), we push it onto the stack.

• Whenever we see a closing bracket (), }, ]):

• The stack must not be empty.

• The top of the stack must be the matching opening bracket.

• If so, we pop it.

• Otherwise, the string is invalid.

At the end:

• If the stack is empty, all brackets are properly matched → true.

• If not empty, there are unmatched opening brackets → false.

We can also simplify checking by mapping closing → opening:

• ')' -> '('

• ']' -> '['

• '}' -> '{'

Algorithm (Step-by-Step):

1. Initialize an empty stack.

2. For each character c in s:

• if c is an opening bracket:

• Push it onto the stack.

• else (it’s a closing bracket):

• if the stack is empty → return false.

• Pop the top element from the stack.

• If the popped element is not the correct matching opening bracket for c → return false.

3. After processing all characters:

• if the stack is empty → return true.

• else → return false.

Pseudo-code:

Complexity:

Let n = |s|:

• Time: O(n) (each char is pushed/popped at most once).

• Space: O(n) in worst case (all opening brackets on stack).

4. Java code:

5. C code:

6. C++ code:

7. Python code:

8.JavaScript code: