298 括号的匹配1 #
- 问题描述
- 辅助栈法解决括号匹配
- 算法流程
问题描述 #
给定一个只包括 ‘(‘，’)’，'{‘，’}’，'[‘，’]’ 的字符串 s ，判断字符串是否有效。 有效字符串需满足：
掌握括号匹配的解法
掌握辅助栈的用法
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
- 每个右括号都有一个对应的相同类型的左括号。
辅助栈法解决括号匹配 #
栈先入后出的特点恰好与本题括号排序特点一致，将输入的字符串挨个输入栈中，如果是左括号直接入栈，如果是右括号则将对应栈顶的左括号出栈，那么遍历完所有括号后栈仍旧为空。
使用哈希表构建左右括号对应关系：键为右括号，值为左括号；这样查询括号是否匹配只需 O(1)时间复杂度；建立栈，遍历字符串并按照算法流程一一判断
算法流程 #
- 遍历字符串
- 对单个字符，如果是左括号则入栈push
- 对单个字符，如果是右括号则进行匹配，判断栈顶字符是否和当前字符匹配，如果不匹配则提前结束；如果匹配，则将此栈顶字符出栈
- 遍历结束后判断栈是否为空，如有剩余字符则返回false
下面是案例：
小结 #
习题 #
- 详细描述算法的流程
- 体会辅助栈在问题中所起的作用
