LeetCode--020--括号匹配

题目描述:

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

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。

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

方法1：

　　遇到左括号压入list中，遇到右括号时先判断list是否为空，是则返回false，否则弹出一个字符与其进行比较，匹配则continue 否则返回false (32ms)

 1 class Solution(object):
 2     def isValid(self, s):
 3         """
 4         :type s: str
 5         :rtype: bool
 6         """
 7         lists = []
 8         i = 0
 9         if len(s) == 1:
10             return False
11         elif len(s) == 0:
12             return True
13         while i < len(s):
14             c = s[i]
15             if c =='(' or c == '[' or c == '{':
16                # if i + 1 != len(s):
17                     # if s[i+1] != ')' and s[i+1] != ']' and s[i+1] != '}':
18                     #     if c < s[i+1]:
19                     #         return False
20                     #([])这种竟然算对，好吧
21                 lists.append(c)
22                 
23             elif c == ')':
24 
25                 if len(lists) != 0:
26                     t = lists.pop()
27                     if t == '(':
28                         i+=1
29                         continue
30                     else:
31                         return False
32                 else:
33                     return False
34             elif c == ']':
35                
36                 if len(lists) != 0:
37                     t = lists.pop()
38                     if t == '[':
39                         i+=1
40                         continue
41                     else:
42                         return False
43                 else:
44                     return False
45             elif c == '}':
46                 
47                 if len(lists) != 0:
48                     t = lists.pop()
49                     if t == '{':
50                         i+=1
51                         continue
52                     else:
53                         return False
54                 else:
55                     return False
56             i += 1
57
58         if len(lists) != 0:
59             return False
60         else:
61             return True

简洁版:(28ms)

 1 class Solution:
 2     def isValid(self, s):
 3         """
 4         :type s: str
 5         :rtype: bool
 6         """
 7         stack = []
 8         for c in s:
 9             if c == '(' or c == '{' or c == '[':
10                 stack.append(c)
11             elif not stack:
12                 return False
13             elif c == ')' and stack.pop() != '(':
14                 return False
15             elif c == '}' and stack.pop() != '{':
16                 return False
17             elif c == ']' and stack.pop() != '[':
18                 return False
19         return not stack

利用字典:(24ms)

 1 class Solution(object):
 2     def isValid(self, s):
 3         """
 4         :type s: str
 5         :rtype: bool
 6         """
 7         pars = [None]
 8         parmap = {')': '(', '}': '{', ']': '['}
 9         for c in s:
10             if c in parmap:
11                 if parmap[c] != pars.pop():
12                     return False
13             else:
14                 pars.append(c)
15         return len(pars) == 1

时间最短:(20ms)

　　用抛出异常的方式把类似)()剔除

 1 class Solution(object):
 2     def isValid(self, s):
 3         """
 4         :type s: str
 5         :rtype: bool
 6         """
 7         try:
 8             stack = []
 9             for key in s :
10                 if(key == '(' or key == '[' or key == '{'):
11                     stack.append(key)
12                 else:
13                     if((key == ')' and stack.pop() == '(') or
14                             (key == ']' and stack.pop() == '[') or
15                             (key == '}' and stack.pop() == '{')):
16                         pass
17                     else:
18                         return False
19             if(len(stack) == 0):
20                 return True
21         except IndexError:
22             return False
23         return False

2018-07-22 18:48:45