題目描述:給定字串 s,忽略大小寫和非字母數字字元,判斷是否為回文。
解題思路:雙指標法:從字串兩端向中間收縮。跳過非字母數字字元(isalnum()),然後比較兩個指標的字元(忽略大小寫,用 tolower() 或 toupper())。若任意一對字元不同則非回文;否則繼續直到指標相遇。
時間複雜度:O(n) — 雙指標最多各移動 n/2 步。
空間複雜度:O(1) — 只用兩個指標。
1. left = 0, right = n - 1 2. While left < right: a. Skip non-alphanumeric from left b. Skip non-alphanumeric from right c. If lowercase(s[left]) != lowercase(s[right]): return false d. left++, right-- 3. Return true
清潔字符串後檢查 O(n) 時間,O(n) 空間:預先過濾英數字,再檢查迴文 — 空間複雜度更差。
正則表達式 O(n) 時間,O(n) 空間:用正則移除非英數,再檢查 — 編譯和匹配開銷。