相关代码已经上传到github：https://github.com/exploitht/leetcode-python

文中代码为了不动官网提供的初始几行代码内容，有一些不规范的地方，比如函数名大小写问题等等；更合理的代码实现参考我的github repo

1、读题

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

The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.

这是经典的栈相关的题，凡是学习数据结构，一般书籍提到栈都会提及括号匹配，解析括号组成的字符串，如果是左括号就入栈，如果是右括号就出栈，看是否匹配。结束的时候再判断一发栈是否为空就行。

2、解题

这道题比较简单，上面读题已经讲到用栈来实现，代码逻辑很简单，如下：

class Solution(object):

    def isValid(self, s):

        """

        :type s: str

        :rtype: bool

        """

        # 循环读取字符串s，如果是左括号则进栈，如果是有括号则出栈

        # 出栈的时候栈不能为空，循环结束的时候栈需要为空

        pars = {'(': 1, '[': 2, '{': 3, ')': -1, ']': -2, '}': -3}

        stack = list()

        for par in s:

            if pars.get(par) > 0:

                stack.append(par)

            else:

                if len(stack) > 0:

                    if pars.get(stack.pop()) == abs(pars.get(par)):

                        continue

                    else:

                        return False

                else:

                    return False

        return True if len(stack) == 0 else False

巴特西

LeetCode专题-Python实现之第20题：Valid Parentheses

1、读题

2、解题

最新文章

热门文章