LeetCode刷题第10天字符串系列之《125回文串验证》

回文串验证》"/>

LeetCode刷题第10天字符串系列之《125回文串验证》

LeetCode 125回文串验证

关于回文串，最早好像是在学校教C语言的时候就让我们写过类似的题目了，不过当时并没有考虑效率什么的，给出的字符串也只是全是字母。

回文串：从左往右和从右往左看是一样的，例如：abba。

题目描述

给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。

说明：本题中，我们将空字符串定义为有效的回文串

要注意的是本题中只考虑字母和数字，所以可能存在其他字符需要先排除掉。

示例

输入: “A man, a plan, a canal: Panama”

输出：true

输入: “race a car”

输出: false

上面例子因为有其他字符和空格，可能不太容易看，而且题目也要求只考虑字母和数字字符，所以先去掉特殊字符并且不考虑大小写，如下：

amanaplanacanalpanama

可以发现从左到右和从右到左都是一样的。

而第二例子,就明显不一样

raceacar

题目解析

按照题目的描述，我们可以先将其他特殊字符给去除掉，简单的方法就是使用正则表达式的方式：

String newString = s.toLowerCase().replaceAll("[^0-9a-z]", "");

其中：

[^0-9a-z]

表示删除所有0-9，a-z之间的字符，即保存数字和小写字母。

处理之后就可以直接比较 第一个字符和最后一个字符，第二个字符和倒数第二个字符…是否相等，如果不相等则表明不是回文串，返回false。

处理方式可以如下：

1. 创建一个队列和栈，先将所有的元素都入队列和进栈。之后根据队列（先进先出）和栈（先进后出）的性质，将队列的队头元素和栈的栈顶元素比较即可判断是否为回文串，代码如下：

public boolean isPalindrome(String s) {if (s == "") {return true;}String newString = s.toLowerCase().replaceAll("[^0-9a-z]", "");		//提前处理字符串Queue<Character> queue = new ArrayDeque<>();	//创建队列Stack<Character> stack = new Stack<>();			//创建栈for (int i = 0; i < newString.length(); i++) {queue.add(newString.charAt(i));stack.add(newString.charAt(i));}for (int i = 0; i < newString.length(); i++) {if (!queue.poll().equals(stack.pop())) {	//队头元素和栈顶元素比较return false;}}return true;}

程序执行结果：

2. 上面那种方法是之前学数据结构的时候教材上给的，其实完全没有必要去用到栈和队列，使用双指针直接比较即可，代码如下：

   public boolean isPalindrome(String s) {if (s == "") {return true;}String newString = s.toLowerCase().replaceAll("[^0-9a-z]", "");		//提前处理字符串for (int i = 0; i < newString.length() / 2; i++) {	//遍历到一半即可if (newString.charAt(i) != newString.charAt(newString.length() - i - 1)) {return false;}}return true;}
   

   程序执行结果：
   

  可见这两种方式虽然可以解题，但是运行速度并不快，原因是因为在提前处理字符串是使用的是正则表达式，比较耗费时间（串的模式匹配）。
  当然不使用正则表达式也是可以的，即不用提前处理字符串，只需在每次比较的过程中直接跳过特殊字符。这样就可以不用调用正则表达式来提前处理字符串了。代码如下：

public boolean isPalindrome(String s) {if (s == "") {return true;}s = s.toLowerCase();int i = 0, j = s.length() - 1;	//双指针while (i < j) {while (!isalnum(s.charAt(i)) && i < j) i++;		//不是字符则跳过while (!isalnum(s.charAt(j)) && i < j) j--;if (s.charAt(i) != s.charAt(j)) {return false;}//比较下一个i++;j--;}return true;
}/*** 判断字符是否是数字或小写字母* 模拟C++中的isalnum* 没有使用java中Character包装类中的相关方法，提高一点速度*/
public boolean isalnum(char ch) {if (ch >= '0' && ch <= '9' || ch >= 'a' && ch <= 'z') {return true;}return false;
}