125. Valid Palindrome

題目說明

給定一個字串 s，判斷它是否為 回文（palindrome）。
條件：

• 只考慮英文字母和數字字元。
• 忽略大小寫。

例子：

• "A man, a plan, a canal: Panama" → true
• "race a car" → false

程式碼
Java 解法（雙指針）

class Solution {
public boolean isPalindrome(String s) {
int left = 0, right = s.length() - 1;
while (left < right) {
while (left < right && !Character.isLetterOrDigit(s.charAt(left))) left++;
while (left < right && !Character.isLetterOrDigit(s.charAt(right))) right--;
if (Character.toLowerCase(s.charAt(left)) != Character.toLowerCase(s.charAt(right))) {
return false;
}
left++;
right--;
}
return true;
}
}

Python 解法

def isPalindrome(s: str) -> bool:
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

複雜度分析

• 時間複雜度：O(n)，每個字元最多檢查一次。
• 空間複雜度：O(1)，只用了雙指針。

Java vs Python 語法差異

在這題裡，兩種語言的差異主要體現在字元判斷與大小寫轉換：

• 判斷是否為字母或數字：

  • Java 用 Character.isLetterOrDigit(c)
  • Python 用 c.isalnum()

• 轉小寫比對：

  • Java 用 Character.toLowerCase(c)
  • Python 用 c.lower()

Java 的語法比較嚴謹，需要呼叫靜態方法；Python 則更直觀，直接用字元的方法即可。

心得

這題讓我體會到資料清理 (data cleaning)的重要性，在演算法題裡，輸入字串可能有空白、標點或大小寫混合，必須先過濾再處理。用雙指針法能邊過濾邊比對，比單純先建立乾淨的新字串再反轉比對更高效，所以要「邊清理邊驗證」，而不只是單純套用演算法。