1. 首页
  2. LeetCode

每日一道 LeetCode (32): 验证回文串

每日一道 LeetCode (32): 验证回文串

每天 3 分钟,走上算法的逆袭之路。

前文合集

每日一道 LeetCode 前文合集

代码仓库

GitHub: https://github.com/meteor1993/LeetCode

Gitee: https://gitee.com/inwsy/LeetCode

题目:验证回文串

题目来源:https://leetcode-cn.com/problems/valid-palindrome/solution/yan-zheng-hui-wen-chuan-by-leetcode-solution/

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

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

示例 1:

输入: "A man, a plan, a canal: Panama"
输出: true

示例 2:

输入: "race a car"
输出: false

解题思路

这种求回文数的题前面出现过,主体思路有两种:

  • 一种是将整个字符串反转,反转后看和原字符串是否相等。
  • 还有一种是双指针,一个指针从前往后迭代,另一个从后往前迭代,逐个比较是否相等。

方案一:双指针

先写自己的答案,这个答案太 2B 了,我就不贴执行效率了。

public boolean isPalindrome(String s) {
    if (s.length() == 0) return true;
    s = s.trim().toLowerCase().replaceAll("[^A-Za-z0-9]", "");
    if (s.length() == 0 || s.length() == 1) return true;
    int len = s.length()/2;
    if (s.length() % 2 > 0) len = len + 1;
    boolean flag = true;
    for (int i = 0; i <= len; i++) {
        if (s.charAt(i) == s.charAt(s.length() - 1 - i)) {
            continue;
        } else {
            flag = false;
            break;
        }
    }
    return flag;
}

我在最开始,对原始字符串先做去除空格,转小写,然后通过正则把其中所有有效的字符全都匹配出来。

这样一个正常字符串被这么处理完成后就成这样了:

# 处理前
Damosel, a poem? A carol? Or a cameo pale? (So mad!)
# 处理后
damoselapoemacaroloracameopalesomad

然后再使用双指针进行判断,这个字符串是否是回文串。

这么看好像执行效率还可以,实际上正则匹配是一个相当耗时的操作,还是乖乖去翻答案吧。

方案二:优化双指针

先放代码:

public boolean isPalindrome_1(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));
        }
    }
    int n = sgood.length();
    int left = 0, right = n - 1;
    while (left < right) {
        if (Character.toLowerCase(sgood.charAt(left)) != Character.toLowerCase(sgood.charAt(right))) {
            return false;
        }
        ++left;
        --right;
    }
    return true;
}

每日一道 LeetCode (32): 验证回文串

答案上这个解析是使用了 JDK 提供的 Character.isLetterOrDigit() 来判断输入的字符是否是字母或者数字,这个方法应该比我刚才的正则要快,下面的那段循环其实大同小异,都是从两边判断字符是否相等。

这个方案好像也挺慢的,它还是要先循环一次,使用整理过后的字符串进行的判断,那么肯定可以直接在原字符串上进行判断,这样可以减少循环的次数。

方案三:原字符串判断

public boolean isPalindrome_2(String s) {
    int n = s.length();
    int left = 0, right = n - 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;
}

每日一道 LeetCode (32): 验证回文串

这个方案就是没有预先处理字符串,直接在一次循环中进行处理,当当前指向的不是有效字符的时候,进行移动指针 ++left--right 操作。

移动完指针以后进行判断,看两个字符是否相等,如果不相等就直接返回 false ,相等的话接着移动一位指针。

这个耗时还有 3ms ,那有没有耗时更短的方案,我在提交的记录中找到了某位不知名的大神的解题方案。

方案四:极致优化

上面这种方案看起来好像已经没有优化的空间了,那怎么还能缩短耗时。

优化 Character.isLetterOrDigit() 这个方法,这个方法的耗时还是有点高的,实际上可以通过 ASCII 直接进行判断当前是否为有效字符。

接着在判断的时候使用 toLowerCase() 这个方法来转小写,而是通过 ASCII 的方式进行转换。

遇到大小写字母的时候,小写字母比其对应的大写字母的 ASCII 码大 32 。

所以如果遇到了大写字母,先加上 32 ,然后再减去 ‘a’ ,就知道其相对于 ‘a’ 的位置了,这个值肯定是小于 32 的,对 32 取余没啥影响。

如果遇到小写字母,虽然加上了 32 ,但是最后对 32 取余了,多加的 32 也就没了,所以还是能得到其相对于 ‘a’ 的正确位置。

大神的思路果然是常人不能企及,一个词来形容下,牛13!!!

下面是代码:

public boolean isPalindrome_3(String s) {
    int left = 0;
    int right = s.length() -1;
    while(left <right) {
        if(!isAlphaNu(s.charAt(left))) {
            left++;
        }
        else if (!isAlphaNu(s.charAt(right))){
            right--;
        }
        else if((s.charAt(left) + 32 - 'a') % 32 != (s.charAt(right) + 32 - 'a') % 32){
            return false;
        }
        else {
            left++;
            right--;
        }
    }
    return true;
}

boolean isAlphaNu(char ch) {
    if (ch >= 'a' && ch <= 'z') return true;
    if (ch >= 'A' && ch <= 'Z') return true;
    if (ch >= '0' && ch <= '9') return true;
    return false;
}

每日一道 LeetCode (32): 验证回文串

今天这道题可以总结一个小套路,遇到字符判断的时候,最高效的方案是使用 ASCII 进行判断,大小写字母中间 ASCII 值相差 32 ,巧用这个差值,可以快速判断大小写字母。

转载声明:本博客由极客挖掘机创作,采用 CC BY 3.0 CN 许可协议。可自由转载、引用,但需署名作者且注明文章出处。如转载至微信公众号,请在文末添加作者公众号二维码。

发表评论

电子邮件地址不会被公开。 必填项已用*标注

QR code