Algorithm Day70 - Valid Parentheses

Posted on In , Views:

🧩 Problem Description

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.
  3. Every close bracket has a corresponding open bracket of the same type.

💬 Examples

Example 1

1
2
Input: s = "()"
Output: true

Example 2

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

Example 3

1
2
Input: s = "(]"
Output: false

Example 4

1
2
Input: s = "([)]"
Output: false

Example 5

1
2
Input: s = "{[]}"
Output: true

💡 Intuition

We can use a stack to track opening brackets:

  • When encountering an opening bracket, push it onto the stack.
  • When encountering a closing bracket, check if it matches the top of the stack.
  • If not matched or stack is empty, return false.
  • At the end, if the stack is empty, the string is valid.

🔢 Java Code (Stack)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import java.util.*;

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

⏱ Complexity Analysis

  • Time: O(n) — each character processed once.
  • Space: O(n) — in worst case stack holds all characters.

✍️ Summary

  • Use stack to validate parentheses.
  • Each closing bracket must match the latest opening bracket.

Related problems

  • lc-22 — Generate Parentheses
  • lc-32 — Longest Valid Parentheses