Valid Parentheses

NeetCode: Valid Parentheses · LeetCode: 20. Valid Parentheses · Difficulty: Easy

Given a string containing only ()[]{}, return true if every bracket is closed by the same type in the correct order.

Example

Text

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

Brute force: keep deleting matched pairs

String.replace returns a new string, because String is immutable. Repeatedly remove any adjacent (), [], or {}. If the string becomes empty it was valid; if no pair can be removed and it isn't empty, it isn't.

Java

class Solution {
    public boolean isValid(String s) {
        while (true) {
            int before = s.length();
            s = s.replace("()", "").replace("[]", "").replace("{}", "");
            if (s.length() == before) {
                return s.isEmpty();
            }
        }
    }
}

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.isValid("[(])"));
        System.out.println(s.isValid("([{}])"));
    }
}

Output

false
true

Time: O(n²), because each round scans the string and there can be n / 2 rounds. Space: O(n).

Optimal: a stack

Push every opening bracket. On a closing bracket, the top of the stack must be its matching opener; pop it. At the end the stack must be empty. The most recent unclosed bracket is always the one that must close first, which is stack behavior. ArrayDeque.pop() throws NoSuchElementException on an empty stack, so each closing bracket checks isEmpty() first (a string such as ")" starts with a closer). stack.pop() != '(' unboxes the Character and compares char values.

Java

import java.util.ArrayDeque;
import java.util.Deque;

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

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.isValid("[(])"));
        System.out.println(s.isValid("([{}])"));
        System.out.println(s.isValid("(("));
        System.out.println(s.isValid(")"));
    }
}

Output

false
true
false
false

Time: O(n). Space: O(n).