[LeetCode]题解（python）：020-Valid Parentheses

题目来源：

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

题意分析：

　　这道题输入一段只包括括号的字符串，判断这个字符串是否已经配对。配对的规则是，每个'(' 和一个 ')'配对，每个'[' 和一个 ']'配对，每个'{' 和一个 '}' 配对，左括号先出现，并且他们之间的字符串也是配对的。比如说“（）[]”两个小括号可以配对，他们之间字符串为空可以配对，两个中括号也如此；所以他是配对的。而“（[）]”，虽然小括号和中括号都有配对，不过小括号之间只有一个中括号，一个中括号不能配对；所以他不能配对。

题目思路：

　　当我们面对一串括号的字符串，首先我们人工的做法是先把确定可以配对的，也就是括号间没有其他字符的先配对，然后去掉，剩下的继续用这种方法去做。要用程序来实现这个过程，我们可以利用堆栈来做，也就是C++里面的stack。如果遇到左括号，我们就将括号push到一个stack里面，如果遇到右括号，那么将stack的队尾pop出，比较是否可以配对，如果可以，继续，如果不可以，返回False。在python里面list也可以当作stack来用。只不过push变成了append。

代码（python）：

 1 class Solution(object):
 2     def match(self,s1,s2):
 3         if s1 == '(' and s2 ==')':
 4             return True
 5         if s1 == '[' and s2 ==']':
 6             return True
 7         if s1 == '{' and s2 =='}':
 8             return True
 9         return False
10     def isValid(self, s):
11         """
12         :type s: str
13         :rtype: bool
14         """
15         ans = []
16         for i in s:
17             if i == '(' or i == '{' or i == '[':
18                 ans.append(i)
19             if i == ')' or i == ']' or i == '}':
20                 if len(ans) == 0:
21                     return False
22                 tmp = ans.pop()
23                 if not self.match(tmp,i):
24                     return False
25         if len(ans) == 0:
26             return True
27         return False

View Code

转载请注明出处：http://www.cnblogs.com/chruny/p/4850436.html