陳憲億 Joseph Chen | Software Engineer & AI Developer

5 min read

1.2k views

這題一開始我寫出來的答案通過了 22/31 個測試，卡在一個很簡單的輸入："0P"。我的程式回傳 True，正確答案是 False。找到 bug 的過程，讓我徹底理解了 Two Pointers 的思維。

題目

給一個字串，只考慮英文字母和數字（忽略大小寫、忽略所有其他符號），判斷它是不是回文（Palindrome）。

Input / Output

Input:  "Was it a car or a cat I saw?"
Output: True
# 只取英數字，全小寫 → "wasitacaroracatisaw" → 是回文

Input:  "0P"
Output: False
# 只取英數字，全小寫 → "0p" → 不是回文

第一版：通過 22/31，卡在 "0P"

我的第一個想法：先把字串整理成只含英文字母的 list，再反轉比較。

第一版 — 有 Bug

class Solution:
    def isPalindrome(self, s: str) -> bool:
        arr = []
        arr2 = []
        input1 = s.lower()

        for i in input1:
            if i >= "A" and i <= "z":   # ← Bug 就在這裡
                arr.append(i)

        for i in reversed(arr):
            if i >= "A" and i <= "z":
                arr2.append(i)

        for i in range(len(arr)):
            if arr[i] == arr2[i]:
                pass
            else:
                return False
        return True

Bug 分析：i >= "A" and i <= "z"

這個範圍檢查是用 ASCII 碼比較。問題在於字串已經 .lower() 過，所以全是小寫。但條件寫的是 "A" 而非 "a"。

ASCII 碼對照

'0' → ASCII 48
'9' → ASCII 57
'A' → ASCII 65   ← 下界
'Z' → ASCII 90
'a' → ASCII 97
'z' → ASCII 122  ← 上界

# '0' 的 ASCII (48) < 'A' 的 ASCII (65)
# 所以 '0' >= 'A' → False
# → 數字 '0' 被過濾掉了！

# 對 "0P".lower() → "0p"：
# '0' 被過濾 → arr = ['p']
# reversed(['p']) = ['p']
# 比較 ['p'] == ['p'] → True  ← 錯誤答案

題目說「英文字母和數字都要考慮」，但我的版本把數字全過濾掉了。只要有數字的測試案例都可能答錯。

除了 Bug，還有個問題：多餘的空間

就算修好 Bug，第一版還是建立了兩個額外的 list（arr 和 arr2），空間複雜度 O(n)。判斷回文根本不需要額外空間——Two Pointers 可以做到 O(1)。

Two Pointers 的核心思維

兩個指針，一個從左、一個從右，向中間靠攏。每次比較左右兩個字元是否相同，不同就回傳 False，相同就繼續往中間走。

# 以 "racecar" 為例

racecar → l=0, r=6 → 'r'=='r' ✅

racecar → l=1, r=5 → 'a'=='a' ✅

racecar → l=2, r=4 → 'c'=='c' ✅

racecar → l=3, r=3 → l >= r，結束 → True

Best Solution：Two Pointers

Best Solution — Two Pointers, O(1) Space

class Solution:
    def isPalindrome(self, s: str) -> bool:
        l = 0
        r = len(s) - 1

        while l < r:
            # 跳過非英數字的字元
            while l < r and not s[l].isalnum():
                l += 1
            while r > l and not s[r].isalnum():
                r -= 1

            # 比較左右兩端
            if s[l].lower() != s[r].lower():
                return False

            l, r = l + 1, r - 1

        return True

⏱ Time: O(n)💾 Space: O(1)

關鍵改進

→s[l].isalnum() 正確處理英文字母和數字，沒有 ASCII 範圍的問題

→不建立任何額外的 list，空間 O(1)

→內層 while 跳過無效字元後才比較，邏輯更清晰

`isalnum()` vs 手動範圍判斷

Python 內建的字串方法，比自己寫 ASCII 範圍判斷更可靠、更易讀：

字串方法對照

# 判斷英數字
'a'.isalnum()   # True   (字母)
'3'.isalnum()   # True   (數字)
'!'.isalnum()   # False  (符號)
' '.isalnum()   # False  (空白)

# 其他常用
'A'.isalpha()   # True   (只有字母)
'3'.isdigit()   # True   (只有數字)
'a'.islower()   # True
'A'.isupper()   # True
'abc'.lower()   # 'abc'
'ABC'.upper()   # 'ABC'

Two Pointers 的使用時機

Palindrome 只是 Two Pointers 的入門。這個模式能解的題型很多：

↔️

從兩端向中間

Valid Palindrome、Container With Most Water

🐢🐇

快慢指針（Slow & Fast）

Linked List Cycle、Remove Duplicates

📏

固定間距

Remove Nth Node From End

✂️

分割條件（Partition）

3Sum、Sort Colors

踩坑的那次 "0P" 讓我記住：永遠用語言內建的方法（isalnum()）而不是自己推 ASCII 範圍。內建方法有完整的邊界處理，自己推很容易遺漏。

EP.03 — Group Anagrams

defaultdict 的正確用法

EP.05 — Sliding Window

Best Time to Buy and Sell Stock

LeetCode

Two Pointers

String

Python

EP.04

Two Pointers從 "0P" 踩坑說起

題目