【Leetcode 筆記】 125. Valid Palindrome

題目解釋

給定一個字串 s，如果它是回文 (palindrome) 則傳回 true，否則傳回 false。

需要統一 downcase 成小寫字母以及移除所有非字母的部分(數字、標點符號等)。

範例

• 輸入: s = "A man, a plan, a canal: Panama"
• 輸出: true

處理後的字串 "amanaplanacanalpanama" 是回文。

最佳解法

步驟

1. 將 s 處理後存為 cleaned_str
2. 令雙指標 left 跟 right
3. 比較 left 與 right 指到的字母是否一樣

程式碼

class Solution:
    def isPalindrome(self, s: str) -> bool:
        cleaned_str = ""
        for i in s:
            if i.isalnum():
                cleaned_str += i.lower()

        left, right = 0, len(cleaned_str) - 1
        while left < right:
            if cleaned_str[left] != cleaned_str[right]:
                return False
            left += 1
            right -= 1
        return True

時間複雜度

O(n)，n 是 s 的字母個數。

空間複雜度

O(n)。

結語

個人感覺要記得 isalnum() 這件事可比用雙指標難多了。

• About
• Latest Posts

數據女巫 𝔻.𝕡𝕪𝕤 🔮

𝐀𝐈 𝐀𝐫𝐭𝐢𝐬𝐭 • 𝐒𝐨𝐟𝐭𝐰𝐚𝐫𝐞 𝐄𝐧𝐠𝐢𝐧𝐞𝐞𝐫
﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊
致力於打破現有框架的 AI 藝術創作者，曾接受藝文雜誌的個人專訪，作品於香港實體展出。有擔任大學講座講師與 Stable Diffusion AI 年會講者的經驗。擅長 Live Prompting，曾獲 GIGABYTE VS AI 街頭對戰冠軍、ASUS 校園 AI 繪圖競賽亞軍等殊榮。
---
歡迎合作邀約 / 委託 / 各式交流
ᴇᴍᴀɪʟ：dpys@techmagichouse.art

Latest posts by 數據女巫 𝔻.𝕡𝕪𝕤 🔮 (see all)

• [資料工程筆記] 資料市集（Data Mart）介紹與在三大雲端服務的工具名詞對照 - 2025-07-25
• [資料工程筆記] 資料倉儲（Data Warehouse）介紹與在三大雲端服務的工具名詞對照 - 2025-07-23
• [資料工程筆記] 資料湖（Data Lake）介紹與在三大雲端服務的工具名詞對照 - 2025-07-21