題目

  • 題目連結
  • 目標函式 : isValid(s)
    • Input : s: str
    • Output : bool

解題概念

  • 題意 : 給予一字串 s (僅會包含 : (、)、{、}、[ 與 ])，要辨別 s 是否為 Vaild
    • 判斷一字串是否為 Valid 的條件 :
      1. 左括號必須由相同類型的括號關閉
      2. 左括號必須依照正確的順序關閉
      3. 每個右括號都有一個相對應相同類型的左括號
  • 此題就是在 Stack 應用中相當經典的一道練習題

我的寫法

  • 想法 :
    1. 如果 s 長度不是偶數，則直接回傳 False (因為 Vaild Parentheses 長度必為偶數)
    2. 使用字典 tmap 去判斷左括號對應之右括號
    3. 使用 for 迴圈依序分析各個元素 item :
      • 若 item 為左括號 : 則直接 Push 進 Stack 中
      • 若 item 為右括號 :
        • 若 Stack 為空 : 則回傳 False
        • 若 Stack.pop() 與 item 彼此不為對應括號 : 則回傳 False
        • 若以上皆非 : 則執行 Stack.pop()
    4. 若迴圈跑完後，Stack仍為非空，則直接回傳 False；若為空，則會傳 True
  • 程式碼 : 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    def isValid(self, s):
        if len(s) % 2 != 0:
            return False
        stack = list()
        left = ["(", "[", "{"]
        tmap = {"(": ")", "[": "]", "{": "}"}
        for item in s:
            if item in left: # ( [ {
                stack.append(item)
            else: # ) ] }
                if len(stack) == 0:
                    return False
                if tmap[stack[-1]] != item:
                    return False
                else:
                    stack.pop(-1)

        if len(stack) != 0:
            return False
        return True
  • 成效 :
    • Time Complexity : $\color{DB4D6D}{O(n)}$
    • Runtime: 11 ms (faster than 86.73%)
    • Memory Usage: 13.5 MB (more than 62.62%)

解答 or 其他優秀寫法 - Part1

  • 想法 :
    • 基本上與我的想法相同，但主要差在它的程式碼更為乾淨，也省去一些不必要的變數宣與判斷條件
  • 程式碼 : 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    def isValid(self, s):

        if len(s) % 2: return False
        
        stack = list()
        tmap = {"(": ")", "[": "]", "{": "}"}
        for item in s:
            if item in tmap:
                stack.append(item)
            elif len(stack) == 0 or tmap[stack.pop()] != item:
                return False

        return len(stack) == 0
  • 成效 :
    • Time Complexity : $\color{DB4D6D}{O(n)}$
    • Runtime: 26 ms (faster than 12.87%)
    • Memory Usage: 13.4 MB (more than 92.13%)

解答 or 其他優秀寫法 - Part2

  • 想法 :
    • 更為乾淨的寫法，將 tmap 的部分捨棄以減少 Memory Usage
  • 程式碼 : 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    def isValid(self, s):

        stack = list()

        for item in s:
            if item == '(':
                stack.append(')')
            elif  item == '[':
                stack.append(']')
            elif  item == '{':
                stack.append('}')
            elif len(stack) == 0 or stack.pop() != item:
                return False
        
        return len(stack) == 0
  • 成效 :
    • Time Complexity : $\color{DB4D6D}{O(n)}$
    • Runtime: 26 ms (faster than 96.34%)
    • Memory Usage: 13.4 MB (more than 92.13%)