Valid Parentheses easy

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

Example 4:

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

Example 5:

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

Steps and Explanation

The problem can be efficiently solved using a stack. We iterate through the string:

1. If we encounter an opening bracket, we push it onto the stack. The stack keeps track of unclosed opening brackets.

2. If we encounter a closing bracket, we check the top of the stack.

   • If the stack is empty (no corresponding opening bracket), the string is invalid.
   • If the top of the stack is the corresponding opening bracket, we pop it from the stack.
   • If the top of the stack is not the corresponding opening bracket, the string is invalid.

3. After iterating through the entire string:

   • If the stack is empty, it means all opening brackets have been correctly closed, and the string is valid.
   • If the stack is not empty, it means there are unclosed opening brackets, and the string is invalid.

Code (C++)

#include <iostream>
#include <stack>
#include <string>

bool isValid(std::string s) {
    std::stack<char> st;
    for (char c : s) {
        if (c == '(' || c == '{' || c == '[') {
            st.push(c);
        } else {
            if (st.empty()) return false; // Unmatched closing bracket
            char top = st.top();
            st.pop();
            if ((c == ')' && top != '(') || (c == '}' && top != '{') || (c == ']' && top != '[')) {
                return false; // Mismatched brackets
            }
        }
    }
    return st.empty(); // True if stack is empty (all brackets matched)
}

int main() {
    std::string s1 = "()";
    std::string s2 = "()[]{}";
    std::string s3 = "(]";
    std::string s4 = "([)]";
    std::string s5 = "{[]}";

    std::cout << isValid(s1) << std::endl; // Output: 1 (true)
    std::cout << isValid(s2) << std::endl; // Output: 1 (true)
    std::cout << isValid(s3) << std::endl; // Output: 0 (false)
    std::cout << isValid(s4) << std::endl; // Output: 0 (false)
    std::cout << isValid(s5) << std::endl; // Output: 1 (true)
    return 0;
}

Complexity Analysis

• Time Complexity: O(N), where N is the length of the string. We iterate through the string once.
• Space Complexity: O(N) in the worst case. The stack can grow up to the size of the input string if the string contains only opening brackets. In the best case (empty string or perfectly balanced parentheses), the space complexity is O(1).