導航頁-LeetCode專題-Python實現

相關代碼已經上傳到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