Back to DSA

Valid Parentheses

easy
Acceptance: 58%
StackString

You receive a string made up exclusively of the bracket characters '(', ')', '{', '}', '[', and ']'. Determine whether the brackets form a correctly nested sequence. A sequence is correct when every opening bracket is paired with a matching closing bracket of the same kind, and brackets close in the proper inside-out order.

Examples

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

Hints

Related Problems

Min StackmediumEvaluate Reverse Polish NotationmediumDaily TemperaturesmediumNext Greater Element IeasyAsteroid Collisionmedium
00:00
import java.util.*;

class Solution {
    public boolean isValid(String s) {
        Deque<Character> stack = new ArrayDeque<>();
        Map<Character, Character> map = Map.of(')', '(', '}', '{', ']', '[');
        for (char c : s.toCharArray()) {
            if (map.containsKey(c)) {
                if (stack.isEmpty() || stack.pop() != map.get(c)) return false;
            } else {
                stack.push(c);
            }
        }
        return stack.isEmpty();
    }
}
Time complexityO(n)
Space complexityO(n)