Valid Parentheses Algorithm

The Valid Parentheses Algorithm is a programming problem that tests a candidate's ability to work with data structures, specifically stacks. The problem statement is simple: given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid. An input string is considered valid if it has the following properties: (1) each open bracket (i.e., '(', '{', '[') is matched by a corresponding close bracket (i.e., ')', '}', ']') of the same type, and (2) each pair of brackets is properly nested within other pairs of brackets. The algorithm is typically solved using a stack data structure, which is a last-in, first-out (LIFO) container that allows for fast insertion and removal of elements. To implement the Valid Parentheses Algorithm, one needs to iterate through the input string and perform the following operations: when encountering an open bracket, push it onto the stack; when encountering a close bracket, pop the top element from the stack and check if it matches the corresponding open bracket. If a match is found, continue processing; otherwise, return false immediately, indicating that the input string is not valid. After processing the entire string, if the stack is empty, this indicates that all open brackets have been matched and closed, meaning the input string is valid. If the stack is not empty, this means there are still unmatched open brackets, so the input string is not valid. This algorithm has a time complexity of O(n), where n is the length of the input string, as it iterates through the string once and performs constant-time operations on the stack.
class Solution {
public:
    bool isValid(string s) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        
        int n = s.size();
        char stack[n];
        int size = 0;
        int hash[256];
        
        hash['('] = 0, hash['{'] = 1, hash['['] = 2;
        hash[')'] = 3, hash['}'] = 4, hash[']'] = 5;
        
        
        for (int i = 0; i < n; i++) {
            if (hash[s[i]] < 3)
                stack[size++] = s[i];
            else {
                if (size == 0) return false;
                if ((hash[s[i]] % 3) != hash[stack[size-1]]) return false;
                size -= 1;
            }
        }
        return size ? false : true;
    }
};

LANGUAGE:

DARK MODE: