【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)

• [推薦工具] 讓程式碼截圖變的美美的吧！VScode CodeSnap 與 3 種同功能線上工具介紹 - 2025-01-05
• [AI 繪圖初級教學] 用 X/Y/Z Plot 比較 Stable Diffusion 的 prompt 與 LoRA 效果 - 2024-12-27
• [AI 繪圖中級篇教學] Stable Diffusion WebUI WD14 Tagger 介紹 - 2024-12-26