【LeetCode 簡單題】6-用Python判斷有效括号

聲明：

今天是第6道題，判斷輸入的隻包含括号的字元串是否有效，有效的條件是左右括号是否比對完畢。以下所有代碼經過樓主驗證都能在LeetCode上執行成功，代碼也是借鑒别人的，在文末會附上參考的部落格連結，如果侵犯了部落客的相關權益，請聯系我删除

（手動比心ღ( ´･ᴗ･` )）

正文

題目：給定一個隻包括 

'('

，

')'

，

'{'

，

'}'

，

'['

，

']'

 的字元串，判斷字元串是否有效。

有效字元串需滿足：

1. 左括号必須用相同類型的右括号閉合。
2. 左括号必須以正确的順序閉合。

注意空字元串可被認為是有效字元串。

示例 1:

輸入: "()"
輸出: true      

示例 2:

輸入: "()[]{}"
輸出: true      

示例 3:

輸入: "(]"
輸出: false      

示例 4:

輸入: "([)]"
輸出: false      

示例 5:

輸入: "{[]}"
輸出: true      

解法1。首先根據題幹條件，如果字元串為空則傳回TRUE，如果長度為奇數則傳回FALSE。先用字典記錄左右括号一一比對關系（左：右），然後對字元串進行周遊的時候如果是左括号就入棧，如果是右括号，如果棧裡沒有元素或者彈出棧裡最後一個入棧的元素對應的鍵值不等于這個右括号的話，就傳回FALSE，周遊完畢後，再判斷stack如果為空，則說明所有字元已經比對完畢，沒有落單，傳回TRUE。

# V 1.0，能送出
class Solution:
    def isValid(self, s):
        if(s is None or len(s) == 0):
            return True
        if len(s) % 2 == 1:
            return False
        stack = []
        dictionary = {'(':')','[':']','{':'}'}
        for each in s:
            if each in dictionary:
                stack.append(each)
            else:
                if not stack or dictionary[stack.pop()] != each:
                    return False
                
        return stack == []
           

解法2。這種解法和上一種解法類似，但是簡化了操作，對左右括号的操作順序反過來了，字典定義的左右映射關系也是反過來的，前面的兩個判斷語句是一樣的。主要流程就是：對字元串周遊-如果是右括号且此右括号對應的左括号與stack裡最後一個入棧的元素相等，則彈出這個元素并繼續周遊，若是左括号則入棧。周遊完畢後判斷stack裡是否隻有None值（左右括号已比對完畢），即判斷長度是否為1，是則傳回TRUE。

# V 2.0，能送出
class Solution:
    def isValid(self, s):
        if(s is None or len(s) == 0):
            return True
        if len(s) % 2 == 1:
            return False
        stack = [None] # 此時stack長度為1
        # print(len(stack))
        dictionary = {')':'(',']':'[','}':'{'}
        for each in s:
            if each in dictionary and dictionary[each] == stack[-1]:
                stack.pop()
            else:
                stack.append(each)
        return len(stack) == 1 # 長度為1的情況是stack裡隻剩下None（初始化時的情況）
           

結尾

解法1：https://blog.csdn.net/qq_34364995/article/details/80274117

解法2：https://blog.csdn.net/qq_34364995/article/details/80274117