LeetCode_字符串_简单_125.验证回文串

小灰灰 2023-10-06 19:32 54阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 1.题目 ##

给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。  
说明：本题中，我们将空字符串定义为有效的回文串。

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

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

**提示：**  
1 <= s.length <= 2 \* 105  
字符串 s 由 ASCII 字符组成

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/valid-palindrome

## 2.思路 ##

（1）双指针  
先将字符串中的字符全部转换为小写，并且再编写一个 judge(char c)，用于判断字符c是否为数字或者小写字母。然后再用指针 i 和 j 分别从前往后、从后往前开始遍历字符串 s。对于指针 i ，从前往后寻找数字字符或者小写字母，同理对于指针 j 也是这样，若能同时找到，则判断这两个字符是否相等，如果不相等，则直接返回 false，否则继续遍历。当字符串能顺利遍历结束，说明 s 是回文串，直接返回 true 即可。

## 3.代码实现（Java） ##

//思路1
    class Solution {
         
        public boolean isPalindrome(String s) {
        
            //将s中的字符全部转换为小写
            s = s.toLowerCase();
            int length = s.length();
            for (int i = 0, j = length - 1; i <= j; i++, j--) {
        
                //从前往后寻找数字字符或者小写字母
                while (i < length - 1 && !judge(s.charAt(i))) {
        
                    i++;
                }
                //从后往前寻找数字字符或者小写字母
                while (j >= 1 && !judge(s.charAt(j))) {
        
                    j--;
                }
                if (i <= j && s.charAt(i) != s.charAt(j)) {
        
                    return false;
                }
            }
            return true;
        }
        
    	//判断字符c是否为数字或者小写字母
        public boolean judge(char c) {
        
            if ((c >= '0' && c <= '9') || (c >= 'a' && c <= 'z')) {
        
                return true;
            } else {
        
                return false;
            }
        }    
    }