LeetCode 125Palindrome verification

About palindrome,At first it seemed to be taught at schoolCWhen we were talking about language, let us write a similar topic,However, efficiency was not considered at the time,The given string is also just all letters.

回文串：Left-to-right and right-to-left look the same,例如：abba.

题目描述

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

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

Note that only letters and numbers are considered in this question,So there may be other characters that need to be excluded first.

示例

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

输出：true

输入: “race a car”

输出: false

The above example is because of other characters and spaces,Might not be easy to see,And the title also requires that only alphanumeric characters be considered,So remove special characters first and ignore case,如下：

amanaplanacanalpanama

It can be found that left-to-right and right-to-left are the same.

And the second example,is obviously different

raceacar

题目解析

按照题目的描述,We can remove other special characters first,The easy way is to use regular expressions：

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

其中：

[^0-9a-z]

表示删除所有0-9,a-z之间的字符,即Save numbers and lowercase letters.

After processing, they can be compared directly 第一个字符和最后一个字符,The second character and the penultimate character…是否相等,If they are not equal then it is not a palindrome,返回false.

The processing method can be as follows：

1. 创建一个队列和栈,All elements are first enqueued and pushed onto the stack.Afterwards according to the queue（先进先出）和栈（先进后出）的性质,Compare the head element of the queue with the top element of the stack to determine whether it is a palindrome,代码如下：

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())) {
    	//The head element is compared to the top element of the stack
            return false;
        }
    }
    return true;

}

程序执行结果：

2. The above method was given in the textbook when I learned data structure before,In fact, there is absolutely no need to use stacks and queues,A direct comparison can be done using two pointers,代码如下：

   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++) {
         	//It can be traversed halfway
           if (newString.charAt(i) != newString.charAt(newString.length() - i - 1)) {
         
               return false;
           }
       }
       
       return true;
   
   }
   

   程序执行结果：
   

  It can be seen that these two methods can solve the problem,But it doesn't run very fast,The reason is because regular expressions are used in advance of the string processing,比较耗费时间（串的模式匹配）.
  Of course it is possible to not use regular expressions,That is, without preprocessing the string,Just skip the special characters directly during each comparison.This way you can preprocess strings without invoking regular expressions.代码如下：

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++;		//Skip if it is not a character
        while (!isalnum(s.charAt(j)) && i < j) j--;
        if (s.charAt(i) != s.charAt(j)) {
    
            return false;
        }
        //比较下一个
        i++;
        j--;
    }

    return true;
}

/** * Determines whether a character is a number or a lowercase letter * 模拟C++中的isalnum * 没有使用java中CharacterThe relevant method in the wrapper class,Speed ​​up a bit */
public boolean isalnum(char ch) {
    
    if (ch >= '0' && ch <= '9' || ch >= 'a' && ch <= 'z') {
    
        return true;
    }
    return false;
}