验证回文串

Myth丶恋晨 2022-12-03 02:23 161阅读 0赞

# 验证回文串 #

## 1、参考资料 ##

https://leetcode-cn.com/problems/valid-palindrome/

## 2、题目要求 ##

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

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

> **示例 1:**

输入: "A man, a plan, a canal: Panama"
    输出: true

> **示例 2:**

输入: "race a car"
    输出: false

## 3、代码思路 ##

我们在字符串 `str` 上定义双指针，`left` 用于指向 `str` 左边的字符，`right` 用于指向 `str` 右边的字符

在移动任意一个指针时，需要不断地向另一指针的方向移动，直到遇到一个字母或数字字符，或者两指针重合为止

然后判断 `left` 指针和 `right` 指针指向的字符是否相同，如果不相同，则表示 `str` 为非回文字符串，返回 `false`；如果当 `left == right` 时，则说明 `str` 满足回文字符串的条件，返回 `true`

## 4、代码实现 ##

代码

/**
     * @ClassName IsPalindromeDmo
     * @Description TODO
     * @Author Heygo
     * @Date 2020/9/1 15:06
     * @Version 1.0
     */
    public class IsPalindromeDmo {
        
    
        public static void main(String[] args) {
        
            boolean isPalindrome = isPalindrome("A man, a plan, a canal: Panama");
            System.out.println(isPalindrome);
        }
    
        /**
         * 判断字符串是否为回文字符串
         * @param str   源字符串
         * @return      true：是回文字符串；false：不是回文字符串
         */
        public static boolean isPalindrome(String str) {
        
    
            // 左指针
            int left = 0;
            // 右指针
            int right = str.length() - 1;
    
            // 左右指针重合时，程序结束
            while (left < right) {
        
                // 如果是非字母数字的字符，则 left 右移，加上 left < right 的条件，防止 left 指针越界
                while (left < right && !Character.isLetterOrDigit(str.charAt(left))) {
        
                    left++;
                }
                // 如果是非字母数字的字符，则 right 左移，加上 left < right 的条件，防止 right 指针越界
                while (left < right && !Character.isLetterOrDigit(str.charAt(right))) {
        
                    right--;
                }
                // 如果左指针和右指针指向的字符相同，则左指针右移，右指针左移，进行下一组字符的判断
                if (Character.toLowerCase(str.charAt(left)) == Character.toLowerCase(str.charAt(right))) {
        
                    left++;
                    right--;
                } else {
        
                    // 否则，返回 false，表示 str 为非回文字符串
                    return false;
                }
            }
    
            // 当 left == right 时，表示 str 回文字符串
            return true;
        }
    
    }