algoadvance

Leetcode 20. Valid Parentheses

Problem Statement

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

Clarifying Questions

  1. Can the input string be empty?
    • Yes, an empty string is considered valid.
  2. What is the maximum length of the string?
    • There is no explicit constraint, but we can assume it fits in memory (typically, up to (10^4) characters).

Strategy

We can solve this problem using a stack to keep track of opening brackets. Here’s the step-by-step strategy:

  1. Initialization:
    • Initialize an empty stack to keep track of open brackets.
  2. Traversal:
    • Traverse the input string character by character.
    • For each character:
      • If it’s an opening bracket ('(', '{', '['), push it onto the stack.
      • If it’s a closing bracket (')', '}', ']'), check the stack:
        • If the stack is empty or the top of the stack is not the matching opening bracket, return false.
        • Otherwise, pop the stack.
  3. Final Check:
    • After processing all characters, if the stack is empty, return true (all open brackets were matched); otherwise, return false.

Code

#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(matchingBrackets.count(c)) {
            if(stack.empty() || stack.top() != matchingBrackets[c]) {
                return false;
            }
            stack.pop();
        } else {
            stack.push(c);
        }
    }

    return stack.empty();
}

int main() {
    std::string s = "()[]{}"; // Change the string according to your test case
    if(isValid(s)) {
        std::cout << "The string is valid." << std::endl;
    } else {
        std::cout << "The string is not valid." << std::endl;
    }

    return 0;
}

Time Complexity

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI