剑指 Offer II 018(Java). 有效的回文（简单）

题目：

给定一个字符串 s ，验证 s 是否是 回文串 ，只考虑字母和数字字符，可以忽略字母的大小写。

本题中，将空字符串定义为有效的 回文串 。

示例 1:

输入: s = "A man, a plan, a canal: Panama"
输出: true
解释："amanaplanacanalpanama" 是回文串
示例 2:

输入: s = "race a car"
输出: false
解释："raceacar" 不是回文串
 

提示：

1 <= s.length <= 2 * 105
字符串 s 由 ASCII 字符组成
 

注意：本题与主站 125 题相同： 

来源：力扣（LeetCode）
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路：

一、双指针（原串+双指针【不适用额外的空间】）

①先跳过非数字和非字母的字符

②再定义双指针left和right，从字符串的头和尾进行遍历，遍历过程中将字母统一转换为小写进行判断是否相同，不同直接返回false,遍历结束以后还没有返回，则说明是回文字符串，返回true。

 1 class Solution {
 2     public boolean isPalindrome(String s) {
 3         int left = 0, right = s.length() - 1;
 4         while (left < right){
 5             while (left < right && !Character.isLetterOrDigit(s.charAt(left))){
 6                 left++;
 7             }
 8             while (left < right && !Character.isLetterOrDigit(s.charAt(right))){
 9                 right--;
10             }
11             if (left < right){
12                 if (Character.toLowerCase(s.charAt(left)) != Character.toLowerCase(s.charAt(right))){
13                     return false;
14                 }
15                 left++;
16                 right--;
17             }
18         }
19         return true;
20     }
21 }

复杂度:

时间复杂度：O(n)，其中n 是字符串s 的长度。

空间复杂度：O(1)。

二、中心扩散法

 ①先去除多余字符，保留所有的字母和数字，同时保留的时候将大写字母转换为小写字母；

②从中心向两边扩散，注意字符个数奇偶数时，左右指针的位置，最后如果能够到达边界，说明是回文返回true，否则返回false。

 1 class Solution {
 2     public boolean isPalindrome(String s) {
 3        StringBuilder sb = new StringBuilder();
 4        for (int i = 0; i < s.length(); i++){
 5            char ch = s.charAt(i);
 6             if (Character.isLetterOrDigit(ch)){
 7                sb.append(Character.toLowerCase(ch));
 8             }
 9         }
10         String ans = new String(sb);
11         int len = ans.length();
12         int left = 0, right = 0;
13         //字符串长度为偶数，则刚好对半分
14         //eg:abba 
15         if (len % 2 == 0){
16             left = len/2 - 1;
17             right = len/2;
18         }else {
19             //eg:abcba
20             left = len/2 - 1;
21             right = len/2 + 1;
22         }
23         while (left >= 0 && right < len && ans.charAt(left) == ans.charAt(right)){
24             left--;
25             right++;
26         }
27         if (left == -1 && right == len){
28             return true;
29         }
30         return false;
31     }
32 }