Algocademy Logo

Valid Parentheses in C++ with O(n) Time Complexity


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.

Example 1:

Input: s = "()"
Output: true

Example 2:

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

Example 3:

Input: s = "(]"
Output: false

Example 4:

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

Example 5:

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

Constraints:

  • 1 <= s.length <= 104
  • s consists of parentheses only '()[]{}'.

Understanding the Problem

The core challenge of this problem is to ensure that every opening bracket has a corresponding closing bracket and that they are correctly nested. This problem is significant in various applications such as parsing expressions in compilers, validating mathematical expressions, and ensuring the correctness of nested structures in code.

Potential pitfalls include mismatched brackets, incorrect nesting, and unbalanced brackets.

Approach

To solve this problem, we can use a stack data structure. The stack helps us keep track of the opening brackets, and we can easily match them with the corresponding closing brackets.

Naive Solution

A naive solution might involve checking each bracket and trying to match it with the corresponding closing bracket. However, this approach is not optimal as it can lead to multiple passes over the string and complex logic to handle nesting.

Optimized Solution

The optimized solution involves using a stack to keep track of the opening brackets. As we iterate through the string, we push each opening bracket onto the stack. When we encounter a closing bracket, we check if it matches the top of the stack. If it does, we pop the stack; otherwise, the string is invalid.

Algorithm

  1. Initialize an empty stack.
  2. Iterate through each character in the string.
  3. If the character is an opening bracket, push it onto the stack.
  4. If the character is a closing bracket, check if the stack is empty or if the top of the stack does not match the corresponding opening bracket. If either condition is true, the string is invalid.
  5. After processing all characters, check if the stack is empty. If it is, the string is valid; otherwise, it is invalid.

Code Implementation


#include <iostream>
#include <stack>
#include <unordered_map>

bool isValid(std::string s) {
    std::stack<char> stack;
    std::unordered_map<char, char> matchingBrackets = {
        {')', '('},
        {']', '['},
        {'}', '{'}
    };

    for (char c : s) {
        // If the character is a closing bracket
        if (matchingBrackets.find(c) != matchingBrackets.end()) {
            // Check if the stack is empty or the top of the stack does not match
            if (stack.empty() || stack.top() != matchingBrackets[c]) {
                return false;
            }
            stack.pop();
        } else {
            // If it's an opening bracket, push it onto the stack
            stack.push(c);
        }
    }

    // If the stack is empty, all brackets were matched correctly
    return stack.empty();
}

int main() {
    std::string s = "{[]}";
    std::cout << (isValid(s) ? "true" : "false") << std::endl;
    return 0;
}

Complexity Analysis

The time complexity of this solution is O(n) because we process each character in the string exactly once. The space complexity is also O(n) in the worst case, where all characters are opening brackets and are pushed onto the stack.

Edge Cases

Potential edge cases include:

Testing

To test the solution comprehensively, consider the following test cases:

Using a testing framework like Google Test can help automate and manage these test cases effectively.

Thinking and Problem-Solving Tips

When approaching such problems, consider using data structures like stacks that are well-suited for managing nested structures. Practice solving similar problems to develop a deeper understanding of common patterns and techniques.

Conclusion

Understanding and solving the valid parentheses problem is crucial for various applications in computer science. By using a stack, we can efficiently check for balanced and correctly nested brackets. Practice and familiarity with data structures will enhance your problem-solving skills.

Additional Resources