給定字串
s，判斷它是否為回文。只考慮英數字元，忽略大小寫。空字串視為回文。
Example:
Input: s = “A man, a plan, a canal: Panama” Output: true
Intuition
TIP
核心思路：用左右指針從兩端往中間逼近，跳過非英數字元，逐一比較。
- 回文的定義是正讀反讀相同，最直覺的做法就是雙指針從兩端比對
- 需要先過濾非英數字元，有兩種策略：預處理成乾淨字串、或在比較時動態跳過
- 動態跳過更省空間，不需額外建立新字串
Approaches
1. Preprocess + Reverse Compare — O(n) / O(n)
- Idea: 先過濾出所有英數字元並轉小寫，再比較原字串與反轉後的字串是否相同
- Time:
O(n)- 過濾一次、反轉一次、比較一次 - Space:
O(n)- 需要儲存過濾後的字串
class Solution {
fun isPalindrome(s: String): Boolean {
val filtered = s.filter { it.isLetterOrDigit() }.lowercase()
return filtered == filtered.reversed()
}
}⭐ 2. Two Pointers (in-place compare) — O(n) / O(1)
- Idea: 左指針從頭、右指針從尾開始，遇到非英數字元就跳過，兩端字元轉小寫後比較，不等則回傳 false
- Time:
O(n)- 每個字元最多被訪問一次 - Space:
O(1)- 只用兩個指針變數
class Solution {
fun isPalindrome(s: String): Boolean {
var left = 0
var right = s.length - 1
while (left < right) {
while (left < right && !s[left].isLetterOrDigit()) left++
while (left < right && !s[right].isLetterOrDigit()) right--
if (s[left].lowercaseChar() != s[right].lowercaseChar()) {
return false
}
left++
right--
}
return true
}
}WARNING
注意內層 while 跳過非英數字元時，必須同時檢查 left < right，否則可能越界。
🔑 Takeaways
- Pattern: 相向雙指針是判斷回文的經典模式
- Key trick: 在比較時動態跳過無關字元，避免額外空間；
isLetterOrDigit()和lowercaseChar()是 Kotlin 處理字元的實用 API