:-: 6.5 验证回文串 ***** **题干：** 给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。 说明：本题中，我们将空字符串定义为有效的回文串。 示例 1: ``` 输入: "A man, a plan, a canal: Panama" 输出: true ``` 示例 2: ``` 输入: "race a car" 输出: false ``` **题目分析：** 验证回文字符串有两种常用方法：二分法与反转法；但此题其中需验证的字符串含有“等等逗号、空格、冒号以及其他不是数字、字母的字符”，有两种常用方法解决：忽略和剔除（正则表达式剔除与手动剔除）；对于大小写统一即可。 **新手有可能遇到的解题思路陷阱：** 没有处理字符串中的其他（不是数字、字母）字符，忽略了大小写问题。 **解题思路分析以及代码实现：** 第一种思路：反转法加正则剔除，对于大小写问题：1.使用String类的toLowerCase()方法统一为小写或者toUpperCase()方法统一为大写；2.使用equalsIgnoreCase()方法忽略大小写。 第一种思路代码： ``` public boolean isPalindrome(String s) { //[^\\da-z]等同于[^a-z^A-Z^0-9] String str = s.replaceAll("[^a-z^A-Z^0-9]", "").toLowerCase();// 统一为小写字母 String reverse = new StringBuffer(str).reverse().toString(); /* * if (reverse.equalsIgnoreCase(str)) {// 忽略的大小写 return true; } */ if (reverse.equals(str)) { return true; } return false; } ``` **复杂度分析** 时间复杂度：O(n)。 空间复杂度：O(n)。 第二种思路：二分法加正则剔除。 第二种思路代码： ``` public boolean isPalindrome(String s) { String str = s.replaceAll("[^a-z^A-Z^0-9]", "").toLowerCase(); char[] ss = str.toCharArray(); int i = 0, j = ss.length - 1; while (i < j) { if (ss[i] != ss[j]) { return false; } i++; j--; } return true; } ``` **复杂度分析** 时间复杂度：O(logn)。 空间复杂度：O(n)。 第三种思路：二分法加忽略，Character.isLetterOrDigit()此方法可判断字符是否是字母、数字，但是此处不用，并且不用String的转换大小写的方法，一切手动来实现，这是因为Java自带的方法功能强大，步骤、判断繁琐，所以对于我们的情况来说，杀鸡焉用宰牛刀，简单适用即可，此外我们也可将判断字符的代码抽离出来，毕竟代码重复了。 第三种思路代码： ``` public boolean isPalindrome(String s) { char[] c = s.toCharArray(); int l = 0; int r = c.length - 1; while (l < r) { while ((l < r) && (c[l] < '0' || c[l] > '9') && (c[l] < 'a' || c[l] > 'z') && (c[l] < 'A' || c[l] > 'Z')) { l++; } while ((r > l) && (c[r] < '0' || c[r] > '9') && (c[r] < 'a' || c[r] > 'z') && (c[r] < 'A' || c[r] > 'Z')) { r--; } if (l > r) break; if (c[l] >= 'a') { c[l] -= 32; } if (c[r] >= 'a') { c[r] -= 32; } if (c[l] == c[r]) { l++; r--; } else { return false; } } return true; } ``` **复杂度分析** 时间复杂度：O(logn)。 空间复杂度：O(n)。 **若有理解错误的、写错的地方、更好的思路，方法，望各位读者评论或者发邮件指正或指点我，不胜感激。**