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

The brackets must close in the correct order.

思路

在考虑这样的题目的时候，边界条件一定要判断清楚。首先，不是说任意一对括号相配对就可以了，还需要考虑括号的种类；其次，括号的配对不能错位嵌套。

本题利用堆栈可以很容易解决。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution(object):
    def isValid(self, s):
        """
        :type s: str
        :rtype: bool
        """
        p = []
        flag = 0
        for i in s:
            if (i == '(' or i == '[' or i == '{'):
                p.append(i)
            else:
                if (len(p)):       
                    j = p.pop()
                    # ord函数可以获得该符号的ASCII码
                    if (ord(i) - ord(j) == 1 or ord(i) - ord(j) == 2):
                        flag = 1
                    else:
                        flag = 0
                        break
                else:
                    flag = 0
                    break
        if (flag and len(p) == 0):
            return True
        else:
            return False