大家好，我是小魔龍，Unity3D軟體工程師，VR、AR，虛拟仿真方向，不定時更新軟體開發技巧，生活感悟，覺得有用記得一鍵三連哦。
一、題目
1、算法題目
“給定一個字元串，驗證它是否是回文串。”
題目連結：
來源：力扣（LeetCode）
連結： 125. 驗證回文串
2、題目描述
給定一個字元串，驗證它是否是回文串，隻考慮字母和數字字元，可以忽略字母的大小寫。
說明： 本題中，我們将空字元串定義為有效的回文串。
示例 1：
輸入: "A man, a plan, a canal: Panama"
輸出: true
解釋： "amanaplanacanalpanama" 是回文串 複制
示例 2：
輸入: "race a car"
輸出: false
解釋： "raceacar" 不是回文串 複制
二、解題
1、思路分析
這道題是考查對于常用字元串中API的使用。
最簡單的方法是對字元串s進行一次周遊，将其中的字母和數字字元進行保留，儲存在另一個字元串sgood中。
這樣就隻需要判斷sgood是否是一個普通的字元串即可。
判斷sgood是否是一個回文串也很簡單，使用API逆序字元串，判斷這兩個字元串是否相同即可。
2、代碼實作
代碼參考：
class Solution {
public boolean isPalindrome(String s) {
StringBuffer sgood = new StringBuffer();
int length = s.length();
for (int i = 0; i < length; i++) {
char ch = s.charAt(i);
if (Character.isLetterOrDigit(ch)) {
sgood.append(Character.toLowerCase(ch));
}
}
StringBuffer sgood_rev = new StringBuffer(sgood).reverse();
return sgood.toString().equals(sgood_rev.toString());
}
} 複制
3、時間複雜度
時間複雜度 ： O(|s|)
其中|s|是字元串s的長度。
空間複雜度： O(|s|)
其中|s|是字元串s的長度，由于需要将所有的字母和數字存放到一個字元串中，在最壞的情況下，得到的新新字元串和原字元串完全相同，是以需要O(|s|)的空間。
三、總結
這道題還可以使用雙指針。
在開始的時候兩個指針分别指向sgood的兩側，随後不斷向中間移動。
每移動一步，判斷這兩個指針指向的字元是否相同，當這兩個指針相遇時，說明sgood是回文串。