Python第 10 期 - 数据结构查看课程总览

298 括号的匹配1

问题描述

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。有效字符串需满足：

栈先入后出的特点恰好与本题括号排序特点一致，将输入的字符串挨个输入栈中，如果是左括号直接入栈，如果是右括号则将对应栈顶的左括号出栈，那么遍历完所有括号后栈仍旧为空。

使用哈希表构建左右括号对应关系：键为右括号，值为左括号；这样查询括号是否匹配只需 O(1)时间复杂度；建立栈，遍历字符串并按照算法流程一一判断

下面是案例：

掌握括号匹配的解法

掌握辅助栈的用法