題目

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

解題概念

我的寫法

  • 想法 : 此題為 Stack 的經典應用題
    1. 將 s 前半部分依序 Push 進 stack 中
    2. 依序瀏覽 s 後半部分的字元，若該字元與 stack.pop() 不同，則直接回傳 false
    3. 若第二步都瀏覽完，且 stack 為空，則回傳 true
  • 程式碼 : 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    def isPalindrome(self, s):
        # 將非數字與非字母的字元移除，同時執行 lower()
        s_new = "".join(i for i in s.lower() if i.isalpha() or i.isdigit())
        print(s_new)

        if len(s_new) <= 1 : return True

        # 前半部分依序 Push 進 stack 中
        stack = list(s_new[0:len(s_new) // 2])

        # 找後半部的起始點
        start = len(s_new) // 2 + 1 if (len(s_new) % 2) else (len(s_new) // 2)

        # 依序瀏覽 s 後半部分的字元
        for i in range(start, len(s_new)):  
            if stack.pop() != s_new[i]:
                return False
        return True
  • 成效 :
    • Time Complexity : $\color{DB4D6D}{O(n)}$
    • Runtime: 29 ms (faster than 87.59%)
    • Memory Usage: 15.6 MB (more than 82.76%)

解答 or 其他優秀寫法

  • 想法 : 使用雙重指標去做 searching
    • 設定指標 left = 0 (陣列前端)
    • 設定指標 right = len(s) - 1 (陣列後端)
    • 使用 while 迴圈，執行 left 往後、right 往前搜尋 :
      • 若 s[left] 不為字母或數字 : 跳過該字元 (left += 1)
      • 若 s[right] 不為字母或數字 : 跳過該字元 (right -= 1)
      • 否則 :
        • 若 s[left] 與 s[right] 不同，則直接回傳 False
        • 不然就 left += 1 並 right -= 1
  • 程式碼 : 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    def isPalindrome(self, s):
        
        left = 0
        right = len(s) - 1

        while left < right:
            if not s[left].isalnum():
                left += 1
            elif not s[right].isalnum():
                right -= 1
            else:
                if s[left].lower() != s[right].lower():
                    return False
                else:
                    left += 1
                    right -= 1

        return True
  • 成效 :
    • Time Complexity : $\color{DB4D6D}{O(n)}$
    • Runtime: 48 ms (faster than 43.17%)
    • Memory Usage: 13.9 MB (more than 99.38%)