一、題目描述

??如果在將所有大寫字符轉(zhuǎn)換為小寫字符、并移除所有非字母數(shù)字字符之后，短語正著讀和反著讀都一樣。則可以認(rèn)為該短語是一個 回文串 。

??字母和數(shù)字都屬于字母數(shù)字字符。

??給你一個字符串 s，如果它是 回文串 ，返回 true ；否則，返回 false 。

二、測試用例

示例 1：

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

示例 2：

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

示例 3：

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

提示：

1 <= s.length <= 2 * 105
s 僅由可打印的 ASCII 字符組成

三、解題思路

1. 基本思路：
   ??頭指針+尾指針，一直判斷是否相等，直到兩指針相遇或者字符不相等停止
2. 具體思路：
   • 預(yù)處理：定義 trim(string& s) 函數(shù)，功能是刪除非字母或數(shù)字的字符，并且字符轉(zhuǎn)小寫。使用雙指針實(shí)現(xiàn)，i 指針用于保存字符，j 指針用于遍歷，遇到要保持的就賦值給 i 指針，最后刪除多余字符。
   • 雙指針遍歷：先使用 trim 函數(shù)處理字符串；因?yàn)榛匚拇行膶ΨQ，所以我們從兩端開始一直判斷是否相同。定義頭指針 i 和尾指針 j ，初始化為 0 和 n-1 。判斷兩指針?biāo)缸址欠裣嗤?#xff0c;相同就繼續(xù)判斷下一個，i++ 和 j-- 。不同則表示不是回文串，返回 false 。直到兩指針相遇都相同，則表示是回文串，返回 true 。

四、參考代碼

時間復(fù)雜度：$\mathrm{O}(n)$
空間復(fù)雜度：$\mathrm{O}(1)$

class Solution {
public:void trim(string& s) {int n = s.length();int i = 0, j = 0;while (j < n) {s[j] = tolower(s[j]);if (isalnum(s[j])) {s[i++] = s[j++];} else {j++;}}s.erase(i, n - i);}bool isPalindrome(string s) {trim(s);int n = s.length();for (int i = 0, j = n - 1; i < j; i++, j--) {if (s[i] != s[j]) {return false;}}return true;}
};