【20190709】【每天一道算法題】有效的括号（棧）

問題

給定一個隻包括 '('，')'，'{'，'}'，'['，']' 的字元串，判斷字元串是否有效。

有效字元串需滿足：左括号必須用相同類型的右括号閉合；左括号必須以正确的順序閉合。

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

示例 1：

輸入："()"，輸出：true

示例 2：

輸入："()[]{}"，輸出：true

示例 3：

輸入："(]"，輸出：false

示例 4：

輸入："([)]"，輸出：false

示例 5：

輸入："{[]}"，輸出：true

思路及解答

1. Python實作

# 方法一：棧操作，不使用哈希表（僅适用于符号類型較少的情況）
# 逐個讀取字元串 s，若棧為空，那麼該元素壓入棧中；若棧不為空，那麼比較目前元素是否和棧頂元素比對，若比對則彈出棧頂元素，若不比對則壓入棧中；最終判斷棧是否為空。
# 時間複雜度：O(n)
class Solution:
    def isValid(self, s: str) -> bool:
        stack = []
        if s == []: 
            return True
        elif len(s) % 2 != 0: 
            return False
        else:
            for ch in s:
                if stack == []:
                    stack.append(ch)
                else:
                    if ch == ")" and stack[-1] == "(":   # stack[-1] 是指棧頂元素（因為 [-1] 索引字元串最後一個元素）
                        stack.pop()
                    elif ch == "]" and stack[-1] == "[":
                        stack.pop()
                    elif ch == "}" and stack[-1] == "{":
                        stack.pop()
                    else:
                        stack.append(ch)
            return stack == []
################## 我最初的寫法 ####################
#### 是錯的，因為棧不是 Python 的内建類型，需要用 Python 清單來模拟基于數組的棧。清單隻能用 .append() 和 .pop()，而棧操作 .peek() 和 .isEmpty() 不能直接使用。
class Solution:
    def isValid(self, s: str) -> bool:
        stack = []
        if s == []: 
            return True
        elif len(s) % 2 != 0: 
            return False
        else:
            for ch in s:
                if stack == []:
                    stack.push(ch)
                else:
                    if ch == "(" and stack.peek() == ")":
                        stack.pop()
                    elif ch == "[" and stack.peek() == "]":
                        stack.pop()
                    elif ch == "{" and stack.peek() == "}":
                        stack.pop()
                    else:
                        stack.push(ch)
            return stack.isEmpty()


# 方法二：棧操作，使用哈希表（适用于符号類型較多的情況）
# 将比對的符号建立哈希表（注意：要反的在前！），然後判斷目前元素是否在哈希表中，若不在則直接壓入棧；若在哈希表中則比較棧頂元素和哈希表中該元素作為 key 對應的 value 是否相同，若不同則傳回False。
# 時間複雜度：O(n)
class Solution:
    def isValid(self, s: str) -> bool:
        stack = []
        hashmap = {")" : "(", "]" : "[", "}" : "{"}   # 建立哈希表。注意：符号都是反的！
        for ch in s:
            if ch in hashmap:   # 判斷 ch 是否存在于哈希表中（.keys() 中）
                top = stack.pop() if stack else "#"  # 若棧為空，那麼棧頂元素置為 ‘#’（隻要不是題目裡的符号即可）
                # if hashmap[ch] == top:     # 不能這樣寫，因為棧為空時不可彈出元素
                #     stack.pop()       
                if hashmap[ch] != top:
                    return False
            else:
                stack.append(ch)
        return not stack
		
''' 聯系：都是先寫反的符号，在寫正的符号；差別：方法一是先判斷才出棧，方法二是先出棧才判斷 '''