710 - Python LeetCode

【Leetcode】python - [125] Valid Palindrome 個人解法筆記 | 內含 python isalpha(), isalnum() 的整理

題目出處

125. Valid Palindrome

難度

easy

個人範例程式碼

class Solution:
    def isPalindrome(self, s: str) -> bool:

        if not s: # input handling, include " "
            return True

        left = 0
        right = len(s)-1 
        s = s.lower()

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

        return True

算法說明

使用 two pointer 前後對照，並使用 isalnum() 排除非字母的內容。

(最近在練習程式碼本身就可以自解釋的 Coding style，可以嘗試直接閱讀程式碼理解)

補充 isalpha(), isalnum()

因為本題敘述中提到 removing all non-alphanumeric characters，因此需要保留「alpha 與 numeric」，
不能只判斷 “字母” 使用 isalpha()。

  • 參考資料：

    • input handling

    注意沒有輸入的時候的處理，另外同時處理 input 為 " " 的情況，
    答案皆為 True (沒有就是 True)

    Boundary conditions

    搜尋範圍為 left < right 區間，此外我們來討論是否需要考慮 left right 的情況

    這邊假設都是一堆特殊符號跟 c，

    如果判斷等於，
    則奇數 cc (自己等於自己) 會多判一次，不影響結果
    偶數 c    c 本來就應該要判斷的，也不影響結果。

    因此本題寫 left < right 或 left <= right，都能得到正確答案。

    Reference