当前位置：首页 > news >正文

LeetCode 验证回文串

news 来源：原创 2024/5/6 8:28:46

验证回文串

CSDN话题挑战赛第2期
参赛话题：学习笔记

这是力扣的125题，写一下思路
如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后，短语正着读和反着读都一样。
则可以认为该短语是一个回文串
字母和数字都属于字母数字字符
在这里插入图片描述

思路题解：

什么是回文串？
例如：
abc cba 、 pgtr rtgp
第一个字符和最后一个字符对应，第二个字符和倒数第二个字符对应，以此类推
条件
有效字符只有 字母 和 数字字符，其他都不是有效字符
要忽略字符的大小写

第一步：
要先从字符串中判断是否为有效字符

public boolean isEffective(char ch){
         // 判断是否是 字母 和数字
        if(Character.isLetter(ch) || Character.isDigit(ch)){
            return true;
        }
        return false;
        // 上面和下面二种方法都可以使用
        //return Character.isLetterOrDigit(ch);
    }

Character.isLetter( ) 是用来判断是否是字母
Character.isDigit( ) 是用来判断是否是数字字符
Character.isLetterOrDigit( ) 是判断当前的字符是否是字母或者是数字字符

第二步：
忽略大小写，可以直接使用toLowerCase()把所有的字符转换为小写字符
最后一步就是判断是否相等

public boolean isPalind(String s){
        s = s.toLowerCase();//把全部字符转换为小写字母
        int left = 0;
        int right = s.length()-1;
        while(left < right){

            while(left < right && !isEffective(s.charAt(left))){
                left++;//判断left是否为有效字符，不是就跳过
            }
            while(left < right && !isEffective(s.charAt(right))){
                right--;//判断right是否为有效字符，不是就跳过
            }
            if(s.charAt(left) != s.charAt(right)){
                return false;
            }
            left++;
            right--;
        }
        return true;
    }

最后判断是否相等可以使用二个下标left 和right，分别指向第一个元素和最后一个元素
它们的执行条件必须是 left 小于 right，判断字符是否有效使用之前写好的isEffective
charAt 是从字符串中获取一个字符
接下来就是使用isEffective来获取有效字符进行判断二个字符是否相等
不相等直接返回 flase ，相等就 left++ right--，判断下一个字符
直到最后跳出循环返回 true

源代码

public boolean isEffective(char ch){
         // 判断是否是 字母 和数字
        if(Character.isLetter(ch) || Character.isDigit(ch)){
            return true;
        }
        return false;

        //return Character.isLetterOrDigit(ch);
    }

    public boolean isPalind(String s){
        s = s.toLowerCase();//把全部字符转换为小写字母
        int left = 0;
        int right = s.length()-1;
        while(left < right){

            while(left < right && !isEffective(s.charAt(left))){
                left++;//判断left是否为有效字符，不是就跳过
            }
            while(left < right && !isEffective(s.charAt(right))){
                right--;//判断right是否为有效字符，不是就跳过
            }
            if(s.charAt(left) != s.charAt(right)){
                return false;
            }
            left++;
            right--;
        }
        return true;
    }