leetcode算法125.验证回文串

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

一、leetcode算法



1、验证回文串


1.1、题目


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


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


示例 1:


输入: “A man, a plan, a canal: Panama”

输出: true

解释:“amanaplanacanalpanama” 是回文串


示例 2:


输入: “race a car”

输出: false

解释:“raceacar” 不是回文串


1.2、思路


思路一:此题我们可以将字符串进行一次遍历,将其中的字母和数字字符拿出来放到另一个字符串中,然后我们只需要判断另一个字符串是否是回文串即可。


1.3、答案


8.png


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());
    }
}


复杂度分析


时间复杂度:O(|s|),其中 |s| 是字符串 s 的长度。


空间复杂度:O(|s|)。由于我们需要将所有的字母和数字字符存放在另一个字符串中,在最坏情况下,新的字符串sgood 与原字符串 s 完全相同,因此需要使用 O(|s|)的空间。

相关文章
|
2月前
|
算法
Leetcode 初级算法 --- 数组篇
Leetcode 初级算法 --- 数组篇
39 0
|
19天前
|
存储 算法 Java
leetcode算法题-有效的括号(简单)
【11月更文挑战第5天】本文介绍了 LeetCode 上“有效的括号”这道题的解法。题目要求判断一个只包含括号字符的字符串是否有效。有效字符串需满足左括号必须用相同类型的右括号闭合,并且左括号必须以正确的顺序闭合。解题思路是使用栈数据结构,遍历字符串时将左括号压入栈中,遇到右括号时检查栈顶元素是否匹配。最后根据栈是否为空来判断字符串中的括号是否有效。示例代码包括 Python 和 Java 版本。
|
2月前
|
监控 算法 数据安全/隐私保护
基于三帧差算法的运动目标检测系统FPGA实现,包含testbench和MATLAB辅助验证程序
本项目展示了基于FPGA与MATLAB实现的三帧差算法运动目标检测。使用Vivado 2019.2和MATLAB 2022a开发环境,通过对比连续三帧图像的像素值变化,有效识别运动区域。项目包括完整无水印的运行效果预览、详细中文注释的代码及操作步骤视频,适合学习和研究。
|
2月前
|
算法
每日一道算法题(Leetcode 20)
每日一道算法题(Leetcode 20)
27 2
|
2月前
【LeetCode 40】98.验证二叉搜索树
【LeetCode 40】98.验证二叉搜索树
13 0
|
4月前
|
算法
测试工程师的技能升级:LeetCode算法挑战与职业成长
这篇文章通过作者亲身体验LeetCode算法题的过程,探讨了测试工程师学习算法的重要性,并强调了算法技能对于测试职业成长的必要性。
70 1
测试工程师的技能升级:LeetCode算法挑战与职业成长
|
4月前
|
算法 C++
第一周算法设计与分析 E : 构造回文串
这篇文章介绍了解决算法问题"构造回文串"的方法,即判断给定的整数N(视为字符串)是否可以通过在前面添加任意个0(或不添加)来构造一个回文串,并给出了相应的C++代码实现。
|
4月前
|
存储 算法 Java
LeetCode经典算法题:打家劫舍java详解
LeetCode经典算法题:打家劫舍java详解
70 2
|
4月前
|
人工智能 算法 Java
LeetCode经典算法题:井字游戏+优势洗牌+Dota2参议院java解法
LeetCode经典算法题:井字游戏+优势洗牌+Dota2参议院java解法
51 1
|
4月前
|
存储 算法 Java
LeetCode经典算法题:预测赢家+香槟塔java解法
LeetCode经典算法题:预测赢家+香槟塔java解法
61 1