每日一道算法题033 验证回文串

题目

leetCode 第 125 题，验证回文串
关联类型：字符串，双指针

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

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

示例 1:

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

输入: "race a car"
输出: false
复制代码

做题时间

class Solution {
    public boolean isPalindrome(String s) {



    }
}
复制代码

以上给出方法输入参数，完成作答。

题目分析

1. 本题使用两种方法
2. 第一种方式是构建一个新的字符串，将符号空格全去掉，然后再将新字符串反转对比
3. 第二种方式是使用双指针，双指针进行对比

解答分析

本文只分析本人做题思路，仅供参考，了解一种解题思想，其他各种做题思路请上网查阅。

方案一

解答成功:
执行耗时:7 ms,击败了20.67% 的Java用户
内存消耗:38.6 MB,击败了41.07% 的Java用户

class Solution {
    public boolean isPalindrome(String s) {
        StringBuilder sb = new StringBuilder();//构建一个新的字符串
        for (int i = 0; i < s.length(); i++) {
            if (Character.isLetterOrDigit(s.charAt(i))) {
                sb.append(s.charAt(i));//只有英文字符及数字进行保存
            }
        }
        String a = sb.toString();
        String b = sb.reverse().toString();
        if (a.equalsIgnoreCase(b)) {//新字符串反转后进行对比
            return true;
        } else {
            return false;
        }
    }
}
复制代码

方案二

解答成功:
执行耗时:3 ms,击败了93.63% 的Java用户
内存消耗:38.3 MB,击败了91.92% 的Java用户

class Solution {
    public boolean isPalindrome(String s) {
        int low = 0, high = s.length() - 1;//使用双指针，一个从前往后，一个从后往前
        while (low < high) {//左侧指针小于右侧指针循环继续
            if (!Character.isLetterOrDigit(s.charAt(low))) {
                low++;//左侧指针处不是英文字符或数字
            } else if (!Character.isLetterOrDigit(s.charAt(high))) {
                high--;//右侧指针处不是英文字符或数字
            } else {
                if (Character.toLowerCase(s.charAt(low))==Character.toLowerCase(s.charAt(high))) {//两指针处字符相同
                    low++;
                    high--;
                } else {//不同直接返回 false
                    return false;
                }
            }
        }
        return true;
    }
}
复制代码