☆打卡算法☆LeetCode 125. 验证回文串 算法解析

推荐阅读

• CSDN主页
• GitHub开源地址
• Unity3D插件分享
• 简书地址
• 我的个人博客
• QQ群：1040082875

大家好，我是小魔龙，Unity3D软件工程师，VR、AR，虚拟仿真方向，不定时更新软件开发技巧，生活感悟，觉得有用记得一键三连哦。

一、题目

1、算法题目

“给定一个字符串，验证它是否是回文串。”

题目链接：

来源：力扣（LeetCode）

链接： 125. 验证回文串

2、题目描述

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

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

示例 1：
输入: "A man, a plan, a canal: Panama"
输出: true
解释： "amanaplanacanalpanama" 是回文串

示例 2：
输入: "race a car"
输出: false
解释： "raceacar" 不是回文串

二、解题

1、思路分析

这道题是考查对于常用字符串中API的使用。

最简单的方法是对字符串s进行一次遍历，将其中的字母和数字字符进行保留，保存在另一个字符串sgood中。

这样就只需要判断sgood是否是一个普通的字符串即可。

判断sgood是否是一个回文串也很简单，使用API逆序字符串，判断这两个字符串是否相同即可。

2、代码实现

代码参考：

class Solution {
    public boolean isPalindrome(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));
            }
        }
        StringBuffer sgood_rev = new StringBuffer(sgood).reverse();
        return sgood.toString().equals(sgood_rev.toString());
    }
}

3、时间复杂度

时间复杂度 ： O(|s|)

其中|s|是字符串s的长度。

空间复杂度： O(|s|)

其中|s|是字符串s的长度，由于需要将所有的字母和数字存放到一个字符串中，在最坏的情况下，得到的新新字符串和原字符串完全相同，因此需要O(|s|)的空间。

三、总结

这道题还可以使用双指针。

在开始的时候两个指针分别指向sgood的两侧，随后不断向中间移动。

每移动一步，判断这两个指针指向的字符是否相同，当这两个指针相遇时，说明sgood是回文串。