1.题目
如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后，短语正着读和反着读都一样。则可以认为该短语是一个 回文串 。
字母和数字都属于字母数字字符。
给你一个字符串 s，如果它是 回文串 ，返回 true；否则，返回false。
2.示例
编辑
3.思路
双指针：
先将字符串通过String的LowerCase方法让字符串所有字符变为小写字符，再通过设置头尾两个指针放置于字符串的头尾，在遍历字符串时候，头尾指针先进行遍历找到合法字符（通过方法Character.isLetterOrDigit方法就能识别该字符是否合法）进行比较。举例来说比如一个字符串
“a ) s a （” 那么头尾指针第一个找到的就是a进行比较，如果相等则头尾指针往中心靠拢一格，直到指针相等或者头指针小于尾部指针
4.代码
LeetCode代码：
class Solution { public boolean isPalindrome(String s) { String str = s.toLowerCase(); int pre = 0; int Des = str.length() - 1; while (pre < Des) { while (pre < Des && !Character.isLetterOrDigit(str.charAt(pre))) { pre++; } while (pre < Des && !Character.isLetterOrDigit(str.charAt(Des))) { Des--; } if (str.charAt(pre) != str.charAt(Des)) { return false; } pre++; Des--; } return true; } }
编辑
总结：时间复杂度为O(n) 空间复杂度为 O(1)
详细案例代码：
package LeetCode1001; public class javaDemo { public static void main(String[] args) { String s = "A man, a plan, a canal: Panama"; // 返回值 boolean flag = true; // 将字符串转为小数 String str = s.toLowerCase(); // 设置头尾指针 int pre=0; int des=str.length()-1; while (pre<=des){ // 在找到相应的合法字符前一直靠拢 while (pre<des && !Character.isLetterOrDigit(str.charAt(pre))){ pre++; } while (des>pre && !Character.isLetterOrDigit(des)){ des--; } // 当两个指针都各就位时候则开始比较,如果字符不匹配则直接返回flase if (str.charAt(pre)!=str.charAt(des)){ flag = false; break; } // 如果两个有效位都一样则继续往中间靠拢 pre++;des--; } // 输出返回值 System.out.println(flag); } }
