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

举报
恬静的小魔龙 发表于 2022/04/25 08:52:05 2022/04/25
【摘要】 推荐阅读CSDN主页GitHub开源地址Unity3D插件分享简书地址我的个人博客QQ群:1040082875大家好,我是小魔龙,Unity3D软件工程师,VR、AR,虚拟仿真方向,不定时更新软件开发技巧,生活感悟,觉得有用记得一键三连哦。 一、题目 1、算法题目“给定一个字符串,验证它是否是回文串。”题目链接:来源:力扣(LeetCode)链接: 125. 验证回文串 2、题目描述给定一...

推荐阅读

大家好,我是小魔龙,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());
    }
}

image.png

3、时间复杂度

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

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

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

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

三、总结

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

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

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

【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息, 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。