一、题目描述
给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。
说明：本题中，我们将空字符串定义为有效的回文串。
示例 1:
输入: "A man, a plan, a canal: Panama"
输出: true
示例 2:
输入: "race a car"
输出: false
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/valid-palindrome
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
二、思考
第一个你要明确什么是回文串，在我们面试的过程中很可能遇到自己没见过的东西，那么你要将问题搞明白以后再去做。虽然这个题是 easy 题目，但是我确实不会，后来百度搜索了下回文串的定义：
“回文串”是一个正读和反读都一样的字符串，比如“level”或者“noon”等等就是回文串。
这样是不是你有所了解了，我们再来看下题目中的 1 个例子：
第一步：初始化左右指针 left\right。
第二步：界定退出条件，如果 left ！= right 则退出，但是如果是我们排除内容项，则进行左右移动过滤掉不符合的情况。
复杂度分析
时间复杂度：O(|s|)，其中 ∣s∣ 是字符串 s 的长度。
空间复杂度：O(1)。
三、实现代码
public static boolean isPalindrome(String s) { //前提：处理特殊情况 if(s == "" || s.length() <=1){ return true; } //第一步、定义左指针和右指针 int left = 0, right = s.length()-1; //当左指针如果>右指针的时候退出，等于号是为了防止出现奇数字符的时候堆成。 while(left <= right){ //左指针的对应的字符 Character charLeft= s.charAt(left); //右指针的对应的字符 Character charRight= s.charAt(right); //如果左指针字符为需要刨除的内容，则左指针移动，否则查看右指针情况 if (Character.isLetterOrDigit(charLeft)){ //如果右指针字符需要刨除的内容，则右指针移动，否则查看两个字符比较的情况 if (Character.isLetterOrDigit(charRight)){ //如果两个不想等则证明不符合回文串正反相同的情况，则直接退出，否则左右指针同时移动进行下一轮的比较 if (!(Character.toLowerCase(charLeft) == Character.toLowerCase(charRight))){ return false; } left++; right--; }else { right--; } }else { left++; } } //最后如果没有比较出来的话，则证明是回文串 return true; }
复制代码
PS：代码复杂度也是一个重大问题，虽然这样属于根据思路顺着写的，但是为了代码简洁，我们看下能否优化下代码逻辑。
public static boolean isPalindrome2(String s) { //前提：处理特殊情况 if(s == "" || s.length() <=1){ return true; } //第一步、定义左指针和右指针 int left = 0, right = s.length()-1; //当左指针如果>右指针的时候退出，等于号是为了防止出现奇数字符的时候堆成。 while(left <= right){ //左指针的对应的字符 Character charLeft= s.charAt(left); //右指针的对应的字符 Character charRight= s.charAt(right); //如果左指针字符为需要刨除的内容，则左指针移动，直到字符为正常字符为止，否则查看右指针情况 while(!Character.isLetterOrDigit(charLeft) && left < right){ left++; charLeft = s.charAt(left); } //如果右指针字符为需要刨除的内容，则右指针移动，直到字符为正常字符为止，否则进行下一步比较操作 while(!Character.isLetterOrDigit(charRight) && right > left){ right--; charRight= s.charAt(right); } //比较如果不相等则直接返回，否则继续同时向中心移动 if (!(Character.toLowerCase(charLeft) == Character.toLowerCase(charRight))){ return false; } left++; right--; } //最后如果没有比较出来的话，则证明是回文串 return true; }
复制代码
5ms 的为第一次的时候，执行出错为 while 循环遍历指针的时候未考虑左指针要始终小于右指针导致下标越界的问题。3ms 为优化后的。虽然感觉运行时间减少了，但是代码行数并未改变，内存消耗反而增多了。
四、小结
除了双指针还有什么方案来实现呢？其实既然是字符串我们直到字符串属于 Java 中的一个非常广泛使用的类。那么我们还知道它为字符的数组。这样我们可以采用如下思路：
第一步：将所有不规范的刨除的标点符号、空格等内容清除掉（利用正则或者循环遍历字符追加到字符串中即可）得到 sourceStr
第二步：反转字符串（有封装好的反转函数，如果要是自己写的话，可以倒着获取数组的字符填充到反转字符串中）,得到 reverseStr
第三步：比较 sourceStr 和 reverseStr 是否相等，如果相等则回文串。反之不是。
时间复杂度和空间复杂度都为 O(n)
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()); }
复制代码
还有 2 种方式就是递归和栈，递归和栈往往是相同存在的可互转。思路如下：你是否还记得我们栈的特性，先进后出
代码用递归的话可以如下方式实现,(栈的话需要再引入一个数据结构可以自己实现下）：
public static boolean isPalindrome3(String s) { return isPalindromeHelper(s, 0, s.length() - 1); }
public static boolean isPalindromeHelper(String s, int left, int right) { if (left >= right) return true; while (left < right && !Character.isLetterOrDigit(s.charAt(left))) left++; while (left < right && !Character.isLetterOrDigit(s.charAt(right))) right--; return Character.toLowerCase(s.charAt(left)) == Character.toLowerCase(s.charAt(right)) && isPalindromeHelper(s, ++left, --right); }
复制代码
评论