这是悦乐书的第174次更新，第176篇原创
01 看题和准备
今天介绍的是LeetCode算法题中Easy级别的第33题（顺位题号是125）。给定一个字符串，确定它是否是回文，只考虑字母数字字符并忽略大小写。空字符串是有效回文。例如：
输入："A man, a plan, a canal: Panama"
输出：true
输入："race a car"
输出：false
本次解题使用的开发工具是eclipse，jdk使用的版本是1.8，环境是win7 64位系统，使用Java语言编写和测试。
02 第一种解法
特殊情况一：当传入的字符串为null时，直接返回true。
特殊情况二：当传入的字符串去掉空格后的长度为0时，直接返回true。
正常情况：因为传入的字符串可能包含特殊字符，如空格、","、":"、"?"等，这些都是非字母、数字字符，这对我们的判断增加了难度，但是其核心思想是不变的。
首先可以将字符串全部转为小写，然后建立两个索引，一个从前往后，一个从后往前，依次获取相应的字符，在判断是否相等前，先要判断获取到的字符是否是字母、数字，不是字母和数字，索引向前移动一位，否则判断两个字符是否相等，不等于直接返回false，如果等于，索引向前移动一位，继续循环，直到遍历完判断完所有的字符。
public boolean isPalindrome(String s) {
if (s == null || s.trim().length() == 0) {
return true;
}
s = s.toLowerCase();
int left = 0;
int right = s.length() - 1;
while (left <= right) {
Character c1 = s.charAt(left);
Character c2 = s.charAt(right);
if (!isAlphaNumeric(c1)) {
left++;
}else if (!isAlphaNumeric(c2)) {
right--;
} else {
if (c1 != c2) {
return false;
}
left++;
right--;
}
}
return true;
}
public static boolean isAlphaNumeric(Character c){
if (c >= 'a' && c<= 'z') {
return true;
}
if (c >= 'A' && c<= 'Z') {
return true;
}
if (c >= '0' && c<= '9') {
return true;
}
return false;
}
03 第二种解法
此解法和第一种解法思路一样，但是借助了Character.isLetterOrDigit()方法来帮我们判断获取到的字符是否为字母或者数字。
public boolean isPalindrome2(String s) {
if (s == null || s.trim().length() == 0) {
return true;
}
s = s.toLowerCase();
int left = 0;
int right = s.length() - 1;
while (left <= right) {
Character c1 = s.charAt(left);
Character c2 = s.charAt(right);
if (!Character.isLetterOrDigit(c1)) {
left++;
} else if (!Character.isLetterOrDigit(c2)) {
right--;
} else {
if (c1 != c2) {
return false;
}
left++;
right--;
}
}
return true;
}
04 另类的解法
此解法不那么正规，利用字符串本身的一些方法以及StringBuffer类的reverse()方法来完成判断。先将传入的字符串转为小写，并且去掉空格，然后利用正则，将非字母、数字的其他字符全部替换掉，再利用StringBuffer的reverse()方法，最后判断两字符串是否相等。
public boolean isPalindrome3(String s) {
if (s == null || s.trim().length() == 0) {
return true;
}
String newString = s.toLowerCase().replace(" ", "").replaceAll("\\W", "");
String newString2 = new StringBuffer(newString).reverse().toString();
return newString.equals(newString2);
}
05 测试与验证
对于上面三种方法，编写了部分测试代码，如下：
public static void main(String[] args) {
Easy_125_ValidPalindrome instance = new Easy_125_ValidPalindrome();
String arg = "A man, a plan, a canal: Panama";
long start = System.nanoTime();
boolean result = instance.isPalindrome(arg);
long end = System.nanoTime();
System.out.println("isPalindrome---输入："+arg+" , 输出："+result+" , 用时："+(end-start)/1000+"微秒");
long start2 = System.nanoTime();
boolean result2 = instance.isPalindrome2(arg);
long end2 = System.nanoTime();
System.out.println("isPalindrome2---输入："+arg+" , 输出："+result2+" , 用时："+(end2-start2)/1000+"微秒");
long start3 = System.nanoTime();
boolean result3 = instance.isPalindrome3(arg);
long end3 = System.nanoTime();
System.out.println("isPalindrome3---输入："+arg+" , 输出："+result3+" , 用时："+(end3-start3)/1000+"微秒");
}
测试结果如下：
isPalindrome---输入：A man, a plan, a canal: Panama , 输出：false , 用时：191微秒
isPalindrome2---输入：A man, a plan, a canal: Panama , 输出：true , 用时：27微秒
isPalindrome3---输入：A man, a plan, a canal: Panama , 输出：true , 用时：1566微秒
06 小结
此三种解法中最优的是解法二，最差的是解法三，如果笔试或者面试碰到此类题，以第二种解法作答较好。
以上就是全部内容，如果大家有什么好的解法思路、建议或者其他问题，可以下方留言交流，点赞、留言、转发就是对我最大的回报和支持！
