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

可以看到，在進(jìn)行判斷的時候，不考慮大小寫，還有其他字符同樣撇開不考慮，只關(guān)心字母字符或數(shù)字是否是回文串。

那么在這里，如果要對給定的字符串進(jìn)行判斷，那么就必須先進(jìn)行篩選，對其他字符進(jìn)行處理。

在這里，對于 Python 而言，考察的是字符串的 isalnum() 方法的使用。

isalnum() 是字符串的一個方法，用以檢測字符串是否由字母和數(shù)字組成。語法如下：

str.isalnum()

對于返回值，如果 str 至少有一個字符且所有字符都是字母或數(shù)字則返回 True，否則返回 False。

現(xiàn)在嘗試使用最暴力的方法，對原字符串進(jìn)行篩選，翻轉(zhuǎn)比較字符串是否相同。代碼如下：

def isPalindrome(self, s: str) -> bool:
    s_filter = ''.join(ch.lower() for ch in s if ch.isalnum())

    return s_filter == s_filter[::-1]

在這里，也可以不翻轉(zhuǎn)字符串進(jìn)行判斷，使用雙指針，代碼如下：

def isPalindrome(self, s: str) -> bool:
    s_filter = ''.join(ch.lower() for ch in s if ch.isalnum())

    length = len(s_filter)

    left = 0
    right = length - 1

    while left < right:
        if s_filter[left] != s_filter[right]:
            return False
        left = left + 1
        right = right - 1

    return True

上面的兩種方法，都是對原字符進(jìn)行篩選處理返回新的字符串進(jìn)行比較?？臻g復(fù)雜度最壞的情況為 O(n)，n 表示字符串 s 的長度，這里最壞就是 s 與處理后的字符串完全相同。

那么現(xiàn)在考慮原字符串上直接進(jìn)行篩選處理，不再額外使用空間存儲。具體處理的做法：

• 初始化雙指針，遍歷字符串；
• 移動左右指針，當(dāng)遇到字母或數(shù)字字符時，進(jìn)行比較；
• 如果左右指針對應(yīng)的元素不同時，返回 False，否則循環(huán)執(zhí)行第二步，直到左右指針相遇。

具體的代碼實現(xiàn)如下。

代碼實現(xiàn)

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

        left = 0
        right = length - 1

        while left < right:
            # 當(dāng)左右指針遇到的是其他非字母數(shù)字時，指針直接往前移動
            while left < right and not s[left].isalnum():
                left += 1
            while left < right and not s[right].isalnum():
                right -= 1

            # 這里注意要轉(zhuǎn)換為小寫進(jìn)行比較，(大寫也可以)
            if s[left].lower() != s[right].lower():
                return False

            left = left + 1
            right = right - 1

        return True

實現(xiàn)結(jié)果

實現(xiàn)結(jié)果

總結(jié)

• 根據(jù)題意以及示例的解釋，可以發(fā)現(xiàn)，除字母數(shù)字字符，其他字符（包括空格字符）在進(jìn)行判斷的時候，可以撇開不考慮。需要注意的是字符的大小寫。
• 那么可以考慮嘗試先對原字符串進(jìn)行篩選處理將結(jié)果存儲在另外的變量中，翻轉(zhuǎn)進(jìn)行比較，如果相同，則表示是回文串；
• 對于上面的方法，除了使用翻轉(zhuǎn)字符串進(jìn)行比較，也可以使用雙指針的方法，移動指針進(jìn)行字符比對。
• 在這里，上面的方法都是基于對原字符串先篩選處理存儲在新的變量中解決問題的。這里可以直接對原字符串進(jìn)行判斷處理，而不需要返回新的結(jié)果。具體的做法：
  • 初始化雙指針，遍歷字符串；
  • 先對指針?biāo)鶎?yīng)的字符進(jìn)行判斷，如果是遇到除字母或數(shù)字的其他字符，直接移動指針。當(dāng)遇到的是字母或數(shù)字，左右指針對應(yīng)的值進(jìn)行比較。
  • 如果左右指針對應(yīng)的值不同時，直接返回 False。否則循環(huán)執(zhí)行第 2 步，直到左右指針相遇。

文章原創(chuàng)，如果覺得有幫助，歡迎點贊關(guān)注。公眾號《書所集錄》同步更新，同樣歡迎關(guān)注點贊。