Cc71fa278411133e2100919caa15604e
(难度Easy)Problem 20: Valid Parentheses(括号匹配)

(难度Easy)Problem 20: Valid Parentheses(括号匹配)

链接

https://leetcode.com/problems/valid-parentheses/

难度等级

Easy

题干

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:
1. Open brackets must be closed by the same type of brackets.
2. Open brackets must be closed in the correct order.
Note that an empty string is also considered valid.

题意

给定一个都是括号的字符串,判断这个字符串里的括号匹配是不是合法的。合法是指所有的左括号都能找到对应匹配的右括号,并且匹配的顺序也要正确。比如)(就被认为是非法的。

样例

Example 1:

Input: "()"
Output: true
Example 2:

Input: "()[]{}"
Output: true
Example 3:

Input: "(]"
Output: false
Example 4:

Input: "([)]"
Output: false
Example 5:

Input: "{[]}"
Output: true

题解

这道题的难度是Easy,可见并不难,很容易想到解法。

我们先把问题假设,原问题当中一共有三种括号。我们先假设只有一种括号的情况,应该怎么处理呢?

观察一下不难找到解法:

如果需要括号合法,只需要保证两点就可以。第一,左括号和右括号的数量相同,这个很简单。第二点,右括号的数量不能超过左括号。

第二点看似是一句废话,其实不然。在我们遍历字符串的时候,不论当前出现了多少左括号都没有关系,只要后面还有足够数量的右括号,就还是有可能完成匹配的。但如果出现了多余的右括号,是永远也无法匹配的,所以一定是非法的。

比如说()),右括号的数量比左括号多一个,它永远也无法匹配了,必然是非法的。

整理一下思路,也就是说我们只需要用一个变量记录当前的左括号的数量,如果遇到了右括号,那么左括号的数量减一。如果右括号的数量大于左括号,那么说明非法,跳出循环。

写成伪代码:

```
def match(str):
for s in str:
if s == '(':

top Created with Sketch.