Given a string containing just the characters "(", ")", "{", "}", "[" and "]", determine if the input string is valid. An input string is valid if open brackets are closed by the same type of brackets and in the correct order.

We use a Stack to track opening brackets. When we encounter an opening bracket, we push it onto the stack. When we encounter a closing bracket, we check if the stack is empty or if the top of the stack matches the corresponding opening bracket. If it matches, we pop; otherwise, the string is invalid.

Time complexity is O(n) as we traverse the string once. Space complexity is O(n) for the stack in the worst case (e.g., all opening brackets).