Course4all
Join us on telegram
Home/dsa/Stack/Valid Parentheses

Valid Parentheses

Master this topic with zero to advance depth.

Valid Parentheses

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.

Visual Representation

s = "{ [ ] }" Step 1: '{' -> Push to Stack. Stack: ['{'] Step 2: '[' -> Push to Stack. Stack: ['{', '['] Step 3: ']' -> Matches Top '['. Pop. Stack: ['{'] Step 4: '}' -> Matches Top '{'. Pop. Stack: [] Result: Valid (Stack is Empty)
Easy

Examples

Input: s = "()[]{}"
Output: true
Approach 1

Level I: Brute Force (String Replace)

Intuition

Regular expressions or string replacements can continuously remove valid adjacent pairs (), {}, [] until the string is empty or no more replacements can be made.

⏱ O(N^2) where N is the length of the string, as `replace` scans the string multiple times.💾 O(N) for string copies during replacement.
java
public class Solution {
    public boolean isValid(String s) {
        while (s.contains("()") || s.contains("{}") || s.contains("[]")) {
            s = s.replace("()", "").replace("{}", "").replace("[]", "");
        }
        return s.isEmpty();
    }
}
Approach 2

Level II: Recursive (Function Call Stack)

Intuition

Instead of an explicit stack object, we can use recursion. Each function call 'expects' a specific closing bracket. If it finds one, it returns; if it finds another opening bracket, it recurses. This demonstrates how the computer's memory uses a stack internally.

⏱ O(N)💾 O(N) due to recursion depth.
java
public class Solution {
    private int i = 0;
    public boolean isValid(String s) {
        return helper(s, '#');
    }
    
    private boolean helper(String s, char expected) {
        while (i < s.length()) {
            char c = s.charAt(i++);
            if (c == '(') { if (!helper(s, ')')) return false; }
            else if (c == '{') { if (!helper(s, '}')) return false; }
            else if (c == '[') { if (!helper(s, ']')) return false; }
            else return c == expected;
        }
        return expected == '#';
    }
}
Approach 3

Level III: Optimal (Stack Mapping)

Intuition

Iterate through the string. If we see an opening bracket, push its corresponding closing bracket onto the stack. If we see a closing bracket, check if it matches the top of the stack. This simplifies the logic by storing what we expect next.

⏱ O(N)💾 O(N)

Detailed Dry Run

CharActionStack StatusMatch?
'('Push ')'[')']-
'['Push ']'[')', ']']-
']'Pop[')']Yes
')'Pop[]Yes
java
import java.util.Stack;

public class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        for (char c : s.toCharArray()) {
            if (c == '(') stack.push(')');
            else if (c == '{') stack.push('}');
            else if (c == '[') stack.push(']');
            else if (stack.isEmpty() || stack.pop() != c) return false;
        }
        return stack.isEmpty();
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.isValid("()[]{}")); // Output: true
    }
}

⚠️ Common Pitfalls & Tips

Be careful with strings that only contain opening brackets, or strings where the stack becomes empty too early.

← Previous QuestionKth Smallest Prime Fraction
Next Question →Min Stack