前言

闲来无事刷题玩，顺带记录一下解题思路，方便未来二刷的时候来找思路。

题目

给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。说明：本题中，我们将空字符串定义为有效的回文串。

示例 ：

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

示例 2: 输入: "race a car" 输出: false
解释："raceacar" 不是回文串

思路

综合题目和示例解释看很容分析，就是把给定的字符串中的所有字母拆出来小写然后组成一个字符串，然后判断字符串是不是回文串。那么题目就分为两部分：1. 拆解字符串s；2. 是否是回文。

• 对于1，可以采取首先小写整个字符串，然后用ASCII码过滤的方式把所有字母取出来。
• 对于2，可用自带的reverse()方法去判断回文，也可以用折半双指针法判断是否是回文。

注：本题有一个很奇怪的现象，不清楚是不是Leetcode官网的编译器的bug，笔者对一下两个方法进行提交的时候都会卡在"OP"这个测试用例上。Leetcode的测试会提示输出为true，但是根据笔者自己在编译器上运行的结果来看测试用例"OP"并没有特殊表现，正常输出false。

Java自带的反转方法

public static boolean isPalindrome(String s) {
    if (s.equals("")||s.length()==0) return true;
    s=s.toLowerCase(); //转小写
    StringBuilder sb=new StringBuilder();
    //提取字母
    for (int i = 0; i <s.length(); i++) {
        if (65 <=s.charAt(i) && s.charAt(i) <=90 || 97 <=s.charAt(i) && s.charAt(i) <=122){
            sb.append(s.charAt(i));
        }
    }
    //直接判断
    return sb.toString().equals(sb.reverse().toString());
}

双指针法

public static boolean isPalindrome(String s) {
    s=s.toLowerCase(); //转小写
    StringBuilder sb=new StringBuilder();
    //提取字母
    for (int i = 0; i <s.length(); i++) {
        if (65 <=s.charAt(i) && s.charAt(i) <=90 || 97 <=s.charAt(i) && s.charAt(i) <=122){
            sb.append(s.toLowerCase().charAt(i));
        }
    }
    //回文反转
    return helper(sb.toString());
}

public static boolean helper(String s){
    if (s.equals("")||s.length()==0) return true;
    //i是头指针，j是尾指针，如果i和j都没有到中间位置，继续循环。
    // 如果相等则跳出循环，整个字符串判断完毕，期间只要发现一对不相等的字符，即可判断为非回文。
    for (int i = 0, j=s.length()-1; i <= s.length()/2 && j>=s.length()/2; i++, j--) {
        if (s.charAt(i)!=s.charAt(j))
            return false;
    }
    return true;
}