LeetCode题解 20.有效的括号

题目描述：

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

有效字符串需满足：

左括号必须用相同类型的右括号闭合。

左括号必须以正确的顺序闭合。

注意空字符串可被认为是有效字符串。

示例 :

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