- 正确答案：括号匹配问题可以通过栈（Stack）数据结构来解决。遍历字符串中的每个字符，当遇到左括号（如 '(', '[', '{'）时，将其压入栈；当遇到右括号（如 ')', ']', '}'）时，检查栈是否为空，若为空则不匹配，否则弹出栈顶元素并判断是否与当前右括号配对。遍历结束后，若栈为空，则说明所有括号都正确匹配，否则不匹配。 - 解答思路： 1. 初始化一个空栈。 2. 遍历输入字符串的每一个字符。 3. 如果字符是左括号（'(', '[', '{'），将其压入栈。 4. 如果字符是右括号（')', ']', '}'）： - 若栈为空，返回 false（没有对应的左括号）。 - 否则弹出栈顶元素，检查是否与当前右括号匹配（例如 '(' 对应 ')'）。 - 若不匹配，返回 false。 5. 遍历完成后，检查栈是否为空。如果为空，返回 true；否则返回 false。 - 深度知识讲解：这个问题考察的是栈的基本应用和对对称性结构的理解。栈是一种后进先出（LIFO, Last In First Out）的数据结构，非常适合处理嵌套或成对出现的结构问题，如括号匹配、HTML标签闭合、函数调用堆栈等。核心原理： - 每个右括号必须与最近的一个未匹配的左括号匹配，这正好符合栈“最后进来的最先处理”的特性。 - 使用哈希表（字典）可以优雅地存储括号之间的映射关系，提高代码可读性和扩展性。时间复杂度：O(n)，其中 n 是字符串长度，每个字符访问一次。空间复杂度：O(n)，最坏情况下所有字符都是左括号，全部入栈。扩展知识点： - 可以扩展到支持多种括号类型，甚至自定义括号对。 - 在编译器设计中，词法分析阶段常使用类似机制检测语法错误。 - 若题目变为“最小添加括号使合法”，则可使用动态规划或计数法求解。 - 代码示例（C++）： ``` #include #include #include #include using namespace std; bool isValid(string s) { stack st; unordered_map mapping = { {')', '('}, {']', '['}, {'}', '{'} }; for (char c : s) { if (c == '(' || c == '[' || c == '{') { st.push(c); } else if (c == ')' || c == ']' || c == '}') { if (st.empty() || st.top() != mapping[c]) { return false; } st.pop(); } } return st.empty(); } int main() { string input; cout << "Enter a string of brackets: "; cin >> input; if (isValid(input)) { cout << "Valid parentheses." << endl; } else { cout << "Invalid parentheses." << endl; } return 0; } ``` - 代码示例（Python）： ``` def is_valid(s: str) -> bool: stack = [] mapping = {')': '(', ']': '[', '}': '{'} for char in s: if char in '([{': stack.append(char) elif char in ')]}': if not stack or stack.pop() != mapping[char]: return False return len(stack) == 0 # 测试用例 print(is_valid("()")) # True print(is_valid("()[]{}")) # True print(is_valid("(]")) # False print(is_valid("([)]")) # False print(is_valid("{[]}")) # True ``` - 常见变种题型： 1. 只有一种括号（如只判断 '(' 和 ')'），可用计数器代替栈，空间复杂度降为 O(1)。 2. 返回第一个不匹配的位置。 3. 给定一个非法括号串，求最少插入多少个括号使其合法。 4. 判断是否为有效嵌套（不允许交叉，如 ([)] 是非法的）。 - 面试注意事项： - 明确题目是否包含其他字符（如字母、数字），通常只关注括号。 - 提前确认括号种类和是否允许混合嵌套。 - 写完代码后建议手动模拟几个测试用例（如 "", "(", "()", "(((", "())"）验证逻辑正确性。

字节 番茄

全站热榜

创作者周榜

字节番茄