Valid Parentheses | Leetcode 20 Solution

Introduction

The “Valid Parentheses” problem (Leetcode 20) is a popular question often asked in coding interviews. The task is to check if a given string containing just the characters ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[‘ and ‘]’ is valid. An input string is valid if the brackets are correctly closed and nested. In this blog post, we’ll explore multiple solutions to this problem, ranging from a naive approach to an optimized solution.

Problem Description

Given a string containing just the characters ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[‘ and ‘]’, determine if the input string is valid. An input string is valid if:

1. Every opening bracket has a corresponding closing bracket.
2. The brackets are properly nested.

Example:

Input: s = "()"
Output: true

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

Input: s = "(]"
Output: false

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

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

Naive Approach (Brute Force) for Valid Parentheses

Approach:

In this approach, we can iterate through the string character by character. For every opening bracket, we find the corresponding closing bracket and check if they match. This solution can become inefficient for larger strings since we need to check each character individually.

Code:

public class Solution {
    public boolean isValid(String s) {
        while (s.contains("()") || s.contains("{}") || s.contains("[]")) {
            s = s.replace("()", "").replace("{}", "").replace("[]", "");
        }
        return s.isEmpty();
    }
}

Explanation:

• The idea here is to keep removing the pairs () , {} , and [] until no more valid pairs can be found.
• If we end up with an empty string, then the parentheses were valid.

Time Complexity:

• O(n^2): The string replace() operation has O(n) time complexity, and it may need to be called multiple times, resulting in a quadratic time complexity.

Space Complexity:

• O(n): The string itself can take up O(n) space, which is the space used in the solution.

Optimized Approach (Using Stack) for Valid Parentheses

Approach:

A more efficient approach uses a stack data structure. We can push each opening bracket onto the stack. For each closing bracket, we check if it matches the top of the stack. If it does, we pop the stack. If it doesn’t, the string is invalid. In the end, if the stack is empty, the string is valid; otherwise, it’s invalid.

Code:

import java.util.Stack;

public 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 != '(') return false;
                if (c == '}' && top != '{') return false;
                if (c == ']' && top != '[') return false;
            }
        }
        
        return stack.isEmpty();
    }
}

Explanation:

• We iterate through each character in the string.
• If the character is an opening bracket, we push it onto the stack.
• If the character is a closing bracket, we check if it matches the bracket at the top of the stack. If it matches, we pop the stack; otherwise, return false.
• In the end, if the stack is empty, it means all opening brackets had corresponding closing brackets.

Time Complexity:

• O(n): We only traverse the string once and perform constant-time operations (push/pop) for each character.

Space Complexity:

• O(n): The stack may hold up to n opening brackets in the worst case (when all characters are opening brackets).

Optimized Approach (Using HashMap) for Valid Parentheses

Approach:

An even more optimized approach is using a HashMap to store the corresponding pairs of brackets. This eliminates the need for multiple if conditions, providing a cleaner solution.

Code:

import java.util.HashMap;
import java.util.Stack;

public class Solution {
    public boolean isValid(String s) {
        HashMap<Character, Character> map = new HashMap<>();
        map.put(')', '(');
        map.put('}', '{');
        map.put(']', '[');

        Stack<Character> stack = new Stack<>();
        
        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();
    }
}

Explanation:

• We use a HashMap to store the pairs of parentheses, which allows us to check if the current closing bracket matches the correct opening bracket.
• If it’s a closing bracket, we check if the top of the stack matches the corresponding opening bracket from the map. If they don’t match, the string is invalid.
• If it’s an opening bracket, we push it onto the stack.

Time Complexity:

• O(n): We traverse the string once and each stack operation (push/pop) is O(1).

Space Complexity:

• O(n): The stack can store up to n characters in the worst case.

Conclusion

We explored three different solutions for the “Valid Parentheses” problem:

1. Naive Approach: Simple but inefficient with time complexity O(n^2).
2. Optimized Approach (Stack): A more efficient approach with O(n) time complexity and O(n) space complexity.
3. Optimized Approach (HashMap): A cleaner solution using a HashMap and stack, still with O(n) time and O(n) space complexity, but more elegant and maintainable.

For interview purposes, the stack-based solution is often the preferred choice due to its efficiency and simplicity.