验证回文串

WangScaler: 一个用心创作的作者。

声明：才疏学浅，如有错误，恳请指正。

[题目]())

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

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

初次分析

首先对字符串里非大小写字母数字进行删除。将删除完的字符串进行前后对比，对比相同即认为是有效的回文串，对比不同的则认为不是回文串。

• 1、对字符串里非大小写字母数字进行删除

  起初我将空格、逗号替换成空字符串，但是测试的时候发现，非大小写字母数字的字符很多种，才发觉这种方式不可行。

  后来则是写了个正则[^A-Za-z0-9]，不是数字大小写字母的进行替换。

• 2、前后对比。我们只需要遍历一半字符串长度，每次遍历前后对比即可。

public static  boolean isPalindrome(String s) {
    s=s.toLowerCase().replaceAll("[^A-Za-z0-9]","").trim();
    if(s.isEmpty()){
        return true;
    }
    for (int i = 0; i < s.length()/2; i++) {
        if(s.charAt(i)!=s.charAt(s.length()-1-i)){
            return false;
        }
    }
    return true;
}

继续分析

看了看答案，官方答案没有这种解法，但是别人写的基本上都是我这种解法。答案的最后一种解法是双指针，我们题目中将非大小写字母数字进行替换的时候会遍历一遍字符串。如果使用双指针的话，则减少了这一次的遍历，也就是说增加一个头指针和一个尾指针代替我们的从头到尾遍历。当指针指向的字符不是大小写字母数字时，直接移动指针。如果符合的话，则进行对比后移动指针。

答案

public boolean isPalindrome(String s) {
        int length = s.length();
        int left = 0, right = length - 1;
        while (left < right) {
            while (left < right && !Character.isLetterOrDigit(s.charAt(left))) {
                ++left;
            }
            while (left < right && !Character.isLetterOrDigit(s.charAt(right))) {
                --right;
            }
            if (left < right) {
                if (Character.toLowerCase(s.charAt(left)) != Character.toLowerCase(s.charAt(right))) {
                    return false;
                }
                ++left;
                --right;
            }
        }
        return true;
    }

复杂度

• 时间复杂度: O(n),其中n是字符串的长度，也就是需要遍历一遍这个字符串。
• 空间复杂度: O(1),需要首尾两个指针记录遍历的位置。

总结

这里用到了两个方法

• isLetterOrDigit：判断字符是不是字母或数字
• toLowerCase：大写转小写

这里的双指针和我的解法本质是一样的，但是时间复杂度上稍微要好些，因为我的解法需要遍历一遍进行替换字符串，然后再遍历一半进行对比。所以这个题还是推荐双指针。其实这个题型前边已经做过很多次了。

都来了，点个赞再走呗！

关注WangScaler，祝你升职、加薪、不提桶！