题目描述:
给定一个只包括 '(',')','{','}','[',']' 的字符串,判断字符串是否有效。
有效字符串需满足:
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。
示例 :
1:
输入: " ( ) "
输出: true
2:
输入: " ( )[ ]{ } "
输出: true
3:
输入: " ( ] "
输出: false
4:
输入: " ( [ ) ] "
输出: false
5:
输入: " { [ ] } "
输出: true
实现思路:
1:遍历括号序列,遇到左括号就进栈等待匹配;若遇到右括号,此时先判断栈是否空,如果栈空则匹配失败,返回False,若栈不空则弹出栈顶元素与之匹配,若匹配失败则返回False,匹配成功则重复以上操作。最终遍历完成后若栈空则代表该括号序列是有效的,返回True, 反之则返回False。
2:在Python中可以利用list(列表)来模拟栈,list.append(),list.pop()分别代表入栈和出栈。然后还需要定义怎样才算匹配,很轻易能想到的是可以判断一对待匹配的左右括号是否在[ '()', '[]', '{}']中。但在这可以利用dict(字典)的键值映射关系来代替。
3: 定义字典 : pre_dict = {')':'(', '}':'{',']':'[' } , 这样左括号在字典的值中pre_dict.values() --> '(', '[', '{',右括号在字典的键中pre_dict.keys() --> ')', ']', '}'。
4: 比如'{ }'的匹配过程如下:首先进来的是'{',为左括号入栈stack.append(' { '),stack = [ ' { ' ]。接着进来'}',为右括号且stack不为空,故弹出栈顶元素' { '进行匹配,可以发现pre_dict['}'] == stack.pop() --> '{' == '{',成功匹配。最后匹配工作已经完成且stack为空,故' { } '是一组有效的括号。
Python代码:
题目链接:https://leetcode-cn.com/problems/valid-parentheses
领取专属 10元无门槛券
私享最新 技术干货