Microsoft OA 面试真题解析：Valid Parentheses 括号匹配与栈

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

• Open brackets must be closed by the same type of brackets.
• Open brackets must be closed in the correct order.

Examples:

Valid input

()
()[]{}
{()}

Invalid input

(]
()[]{({)}

这道题要求判断括号字符串是否有效，核心思路是用栈按顺序匹配左括号与右括号。遍历字符串时，遇到左括号就入栈；遇到右括号时，检查栈顶是否是对应类型的左括号，如果不匹配或栈已空，直接返回无效。遍历结束后，如果栈为空，说明所有括号都正确闭合且顺序合法，否则仍有未匹配的左括号。这个问题非常典型，重点在于理解“后进先出”的栈结构如何保证嵌套括号的正确性。