Problem Informations

• Problem Index: 20
• Problem Link: Valid Parentheses
• Topics: String, Stack

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.

Example 1:

Input: s = “()”

Output: true

Example 2:

Input: s = “()[]{}”

Output: true

Example 3:

Input: s = “(]”

Output: false

Example 4:

Input: s = “([])”

Output: true

Constraints:

• $1 \leq s.length \leq 10^4$
• $s$ consists of parentheses only '()[]{}'.

Intuition

The problem requires verification of whether a string consisting solely of different types of brackets is valid. A valid string is one where each type of opening bracket is correctly closed by the same type of bracket and in the correct order. This intuition suggests a need for a mechanism that can keep track of unmatched opening brackets as we process the string from left to right. A stack data structure is suitable for this purpose because it follows the Last In, First Out (LIFO) principle, which aligns well with the requirement to match the most recently opened bracket with a corresponding closing bracket.

Approach

The given C++ solution utilizes a stack to validate the bracket sequence in the string. The strategy involves iterating over each character in the string:

1. Opening Bracket Handling: For any opening bracket encountered ('(', '{', '['), an expected corresponding closing bracket (')', '}', ']') is pushed onto the stack. This prepares the stack to verify upcoming closing brackets.

2. Closing Bracket Verification: When a closing bracket is encountered, the algorithm checks:

   • If the stack is empty, which indicates that there is no opening bracket available for pairing, thus the input string is invalid.
   • If the stack is not empty, the top of the stack (which contains the expected closing bracket to match the most recent unmatched opening bracket) is compared to the current closing bracket. If they do not match, it indicates a mismatch in the bracket type, and the input string is invalid.

3. Final Validation: At the end of the string traversal, the stack should be empty if every opening bracket has been matched with a corresponding closing bracket. An empty stack signifies that the sequence of brackets was completely balanced and valid.

Through this method, the algorithm efficiently checks for balanced and properly nested brackets using a stack, ensuring each closing bracket matches the most recent unmatched opening bracket. This approach achieves linear time complexity, $O(n)$, where $n$ is the length of the string, by processing each character exactly once.

Code

C++

class Solution {
public:
    bool isValid(string s) {
        stack<char> bracketStack;
        
        for (char currentChar : s) {
            // Push expected closing bracket onto the stack for each opening bracket
            if (currentChar == '(') {
                bracketStack.push(')');
            } else if (currentChar == '[') {
                bracketStack.push(']');
            } else if (currentChar == '{') {
                bracketStack.push('}');
            } 
            // If a closing bracket is found, check for matching opening bracket
            else {
                if (bracketStack.empty() || currentChar != bracketStack.top()) {
                    return false; // No matching opening bracket or mismatch
                }
                bracketStack.pop(); // Pop the matching opening bracket
            }
        }

        // Stack should be empty if all opening brackets have matching closing brackets
        return bracketStack.empty();
    }
};

Python

class Solution:
    def isValid(self, s: str) -> bool:
        bracketStack = []

        for currentChar in s:
            # Push expected closing bracket onto the stack for each opening bracket
            if currentChar == '(':
                bracketStack.append(')')
            elif currentChar == '[':
                bracketStack.append(']')
            elif currentChar == '{':
                bracketStack.append('}')
            # If a closing bracket is found, check for matching opening bracket
            else:
                if not bracketStack or currentChar != bracketStack[-1]:
                    return False  # No matching opening bracket or mismatch
                bracketStack.pop()  # Pop the matching opening bracket

        # Stack should be empty if all opening brackets have matching closing brackets
        return not bracketStack

Complexity

• Time complexity: $O(n)$

The time complexity is $O(n)$, where $n$ is the length of the input string s. This is because we iterate over each character in the string exactly once in the for-loop, performing a constant amount of work (either pushing or popping from the stack) for each character.

• Space complexity: $O(n)$

The space complexity is $O(n)$ in the worst case. In a scenario where all characters are opening brackets, we would push all characters onto the stack, leading to a maximum stack size proportional to the input size $n$. In the general case, however, the space used by the stack depends on the number of unmatched opening brackets, but is bounded by $n$.