LeetCode 解題思路：125. Valid Palindrome（有效回文）

題目描述

如果在將所有大寫字符轉換為小寫字符、並移除所有非字母數字字符之後，短語正著讀和反著讀都一樣，則可以認為該短語是一個回文串。

字母和數字都屬於字母數字字符。

給定一個字串 s，驗證它是否是回文串，只考慮字母和數字字符，可以忽略字母的大小寫。

範例 1：

輸入：s = "A man, a plan, a canal: Panama"
輸出：true
解釋："amanaplanacanalpanama" 是回文串

範例 2：

輸入：s = "race a car"
輸出：false
解釋："raceacar" 不是回文串

範例 3：

輸入：s = " "
輸出：true
解釋：在移除非字母數字字符之後，s 是一個空字串 ""
由於空字串正著反著讀都一樣，所以是回文串

限制條件：

• 1 <= s.length <= 2 * 10^5
• 字串 s 由 ASCII 字符組成

解法一：字串預處理 + 反轉比較

思路

先將字串清理（去除非字母數字字符並轉小寫），然後比較處理後的字串與其反轉是否相同。

程式碼

def isPalindrome(s):
    # 步驟1：過濾非字母數字字符並轉小寫
    cleaned = ""
    for char in s:
        if char.isalnum():
            cleaned += char.lower()
    
    # 步驟2：比較字串與其反轉
    return cleaned == cleaned[::-1]

執行過程示例

輸入：s = "A man, a plan, a canal: Panama"

步驟1：過濾處理
'A' -> 'a' ✓
' ' -> 跳過
'm' -> 'm' ✓
'a' -> 'a' ✓
'n' -> 'n' ✓
',' -> 跳過
' ' -> 跳過
...

cleaned = "amanaplanacanalpanama"

步驟2：比較
cleaned          = "amanaplanacanalpanama"
cleaned[::-1]    = "amanaplanacanalpanama"
兩者相同 → 返回 True

複雜度分析

• 時間複雜度：O(n)
  • 遍歷字串：O(n)
  • 字串反轉：O(n)
  • 字串比較：O(n)
• 空間複雜度：O(n)
  • 需要額外空間存儲清理後的字串

解法二：雙指針法（最優解）

思路

使用左右兩個指針，分別從字串兩端向中間移動，跳過非字母數字字符，只比較有效字符。

程式碼

def isPalindrome(s):
    left, right = 0, len(s) - 1
    
    while left < right:
        # 左指針跳過非字母數字字符
        while left < right and not s[left].isalnum():
            left += 1
        
        # 右指針跳過非字母數字字符
        while left < right and not s[right].isalnum():
            right -= 1
        
        # 比較當前字符（轉小寫）
        if s[left].lower() != s[right].lower():
            return False
        
        # 移動指針
        left += 1
        right -= 1
    
    return True

執行過程示例

輸入：s = "A man, a plan, a canal: Panama"

初始狀態：
A   m a n ,   a   p l a n   a   c a n a l :   P a n a m a
^                                                       ^
left=0                                              right=32

第1輪比較：
left=0: 'A' (字母) vs right=32: 'a' (字母)
'A'.lower() == 'a'.lower() → 'a' == 'a' ✓
left=1, right=31

第2輪比較：
left=1: ' ' → 跳過 → left=2: 'm'
right=31: 'm' 
'm'.lower() == 'm'.lower() → 'm' == 'm' ✓
left=3, right=30

...繼續直到 left >= right

詳細步驟追蹤

步驟    left  right  s[left]  s[right]  比較結果
1       0     32     'A'      'a'       'a' == 'a' ✓
2       2     31     'm'      'm'       'm' == 'm' ✓  
3       3     30     'a'      'a'       'a' == 'a' ✓
4       4     29     'n'      'n'       'n' == 'n' ✓
5       6     27     'a'      'a'       'a' == 'a' ✓
6       8     26     'p'      'P'       'p' == 'p' ✓
...
結果：True（所有比較都相同）

複雜度分析

• 時間複雜度：O(n)
  • 每個字符最多被訪問一次
• 空間複雜度：O(1)
  • 只使用兩個指針變數

解法三：使用正則表達式

思路

使用正則表達式一次性清理字串，然後進行回文判斷。

程式碼

import re

def isPalindrome(s):
    # 使用正則表達式去除非字母數字字符
    cleaned = re.sub(r'[^a-zA-Z0-9]', '', s).lower()
    return cleaned == cleaned[::-1]

複雜度分析

• 時間複雜度：O(n)
• 空間複雜度：O(n)

解法四：遞迴解法

思路

使用遞迴的方式實現雙指針邏輯。

程式碼

def isPalindrome(s):
    def is_valid_palindrome(left, right):
        # 基本情況
        if left >= right:
            return True
        
        # 跳過左邊的非字母數字字符
        if not s[left].isalnum():
            return is_valid_palindrome(left + 1, right)
        
        # 跳過右邊的非字母數字字符
        if not s[right].isalnum():
            return is_valid_palindrome(left, right - 1)
        
        # 比較字符
        if s[left].lower() != s[right].lower():
            return False
        
        # 遞迴檢查內部
        return is_valid_palindrome(left + 1, right - 1)
    
    return is_valid_palindrome(0, len(s) - 1)

複雜度分析

• 時間複雜度：O(n)
• 空間複雜度：O(n)（遞迴調用棧）

解法比較表格

重要觀念總結

1. 字符處理技巧

# Python 內建方法
char.isalnum()    # 判斷是否為字母或數字
char.isalpha()    # 判斷是否為字母
char.isdigit()    # 判斷是否為數字
char.lower()      # 轉換為小寫
char.upper()      # 轉換為大寫

2. 雙指針模式

雙指針是解決回文問題的經典模式：

• 初始化：left = 0, right = len(s) - 1
• 移動條件：while left < right
• 跳過無效字符：使用內層while循環
• 比較邏輯：統一轉換格式後比較

3. 邊界條件處理

# 重要的邊界檢查
while left < right and not s[left].isalnum():
    left += 1
# 確保 left < right 避免指針交叉

4. 空間優化思維

• 預處理方法：簡單但需要O(n)額外空間
• 雙指針方法：複雜但只需要O(1)空間
• 在面試中通常優先考慮空間優化的解法

面試加分點

1. 討論多種解法：展示思維的完整性
2. 空間優化：從O(n)優化到O(1)的思路
3. 邊界處理：正確處理指針邊界
4. 代碼簡潔性：避免重複邏輯

常見錯誤

1. 指針越界：忘記檢查 left < right
2. 字符處理：忘記轉換大小寫
3. 邊界情況：沒有正確處理空字串
4. 邏輯錯誤：跳過字符的條件寫錯

# 錯誤示例
while not s[left].isalnum():  # 缺少邊界檢查
    left += 1

# 正確示例  
while left < right and not s[left].isalnum():
    left += 1

相關題目拓展

1. 9. Palindrome Number：數字回文判斷
2. 5. Longest Palindromic Substring：最長回文子串
3. 647. Palindromic Substrings：回文子串計數
4. 680. Valid Palindrome II：允許刪除一個字符的回文

進階思考

1. 如何處理 Unicode 字符？
2. 如何擴展到忽略空格但保留標點符號？
3. 能否在不轉換大小寫的情況下比較？

# Unicode 考慮
def isPalindrome(s):
    # 使用 unicodedata 正規化
    import unicodedata
    s = unicodedata.normalize('NFKD', s)
    # ... 其餘邏輯相同

這道題目是雙指針技巧的經典應用，掌握了這個pattern，對解決其他相關問題很有幫助！