namespace LeetCode.Logic;

public class BracketValidator
{
    /// <summary>
    /// Time Complexity: O(n) - We traverse the string exactly once.
    /// Space Complexity: O(n) - In the worst case (e.g., all open brackets), the stack stores all characters.
    /// </summary>
    public bool IsValid(string s)
    {
        var stack = new Stack<char>();

        foreach (char c in s)
        {
            // If it's an opening bracket, push it onto the stack
            if (c == '(' || c == '{' || c == '[')
            {
                stack.Push(c);
            }
            else
            {
                // If we find a closing bracket but the stack is empty, it's invalid
                if (stack.Count == 0) return false;

                char open = stack.Pop();

                // Check if the popped opening bracket matches the current closing bracket
                if (c == ')' && open != '(') return false;
                if (c == '}' && open != '{') return false;
                if (c == ']' && open != '[') return false;
            }
        }

        // If the stack is empty, all brackets were matched correctly
        return stack.Count == 0;
    }
}