Problem 21 - Valid Parentheses

Explore our archive for previous posts.

Question

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.

Example 1:

Input: s = "()"
Output: true

Example 2:

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

Example 3:

Input: s = "(]"
Output: false

Constraints:

• 1 <= s.length <= 104

• s consists of parentheses only '()[]{}'.

Approach

This solution uses a stack to check the validity of parentheses in a given string. It iterates through each character in the string and performs the following operations:

1. If an opening parenthesis is encountered (i.e., '(', '{', or '['), it is pushed onto the stack.

2. If a closing parenthesis is encountered (i.e., ')', '}', or ']'), it is compared with the top element of the stack.

   • If they form a valid pair (e.g., '()' or '{}'), the top element is popped from the stack.

   • If they do not form a valid pair, the string is not valid, and the function returns false.

3. After iterating through all the characters, the function checks if the stack is empty. If it is, the string is valid; otherwise, it is not.

Solution

Solve it here

import java.util.Stack;

class Solution {
    public boolean isValid(String s) {

        // Stack to hold opening parentheses
        Stack<Character> stack = new Stack<>(); 

        for (char c : s.toCharArray()) {
            if (c == '(' || c == '{' || c == '[') {
                // Push opening parentheses onto the stack
                stack.push(c); 
            } else if (c == ')' && !stack.isEmpty() && stack.peek() == '(') {
                // Matching closing parenthesis found, pop the corresponding opening parenthesis
                stack.pop();
            } else if (c == '}' && !stack.isEmpty() && stack.peek() == '{') {
                // Matching closing parenthesis found, pop the corresponding opening parenthesis
                stack.pop(); 
            } else if (c == ']' && !stack.isEmpty() && stack.peek() == '[') {
                // Matching closing parenthesis found, pop the corresponding opening parenthesis
                stack.pop();
            } else {
                // Invalid parentheses, return false
                return false; 
            }
        }

        // The string is valid if the stack is empty
        return stack.isEmpty(); 
    }
}

Time and space complexity

Time Complexity: The time complexity of this solution is O(n), where 'n' is the length of the input string 's'. The algorithm iterates through each character of the string exactly once.

Space Complexity: The space complexity is O(n) as well. In the worst case, when all opening parentheses are present in the string, the stack will hold all of them, requiring space proportional to the length of the string 's'.

Explore more?

Missed a previous edition? Catch up on the insightful content you might have missed by visiting our archive here. Thank you for being a valued reader of our newsletter. We appreciate your continued support!