LeetCode 125、验证回文串

本题和 LeetCode 9、回文数的解题思路是一样的。

一、题目描述

如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后，短语正着读和反着读都一样。则可以认为该短语是一个 回文串 。

字母和数字都属于字母数字字符。

给你一个字符串 s，如果它是 回文串 ，返回 true ；否则，返回 false 。

示例 1：

输入: s = "A man, a plan, a canal: Panama" **输出：**true 解释："amanaplanacanalpanama" 是回文串。

示例 2：

**输入：**s = "race a car" **输出：**false 解释："raceacar" 不是回文串。

示例 3：

**输入：**s = " " **输出：**true **解释：**在移除非字母数字字符之后，s 是一个空字符串 "" 。由于空字符串正着反着读都一样，所以是回文串。

提示：

1 <= s.length <= 2 * 10^5
s 仅由可打印的 ASCII 字符组成

二、题目解析

三、参考代码

public class Solution {  
    public boolean isPalindrome(String s) {  
        // isalnum()方法检测字符串是否由字母和数字组成  
        StringBuilder xArray = new StringBuilder();  
        for (char ch : s.toCharArray()) {  
            if (Character.isAlphabetic(ch) || Character.isDigit(ch)) {  
                xArray.append(Character.toLowerCase(ch));  
            }  
        }  
  
        // 左边索引的位置在 0  
        int left = 0;  
  
        // 右边索引的位置在 xArray.length - 1  
        int right = xArray.length() - 1;  
  
        // 两个索引向内移动  
        // left 向右移动  
        // right 向左移动  
        while (left <= right) {  
            // 判断这两个元素值是否相同  
            if (xArray.charAt(left) != xArray.charAt(right)) {  
                // 如果不同，直接返回 false  
                return false;  
            }  
  
            // 否则，left 向右移动  
            left++;  
        }  
          
        // right 向左移动，此处不再需要，因为在上面的循环中已经结束循环了。  
        // right--;  
        return true;  
    }  
}

参考代码

class Solution:
    def isPalindrome(self, s: str) -> bool:

        # isalnum() 方法检测字符串是否由字母和数字组成
        # 转换为字符串数组的形式
        xArray = "".join(ch.lower() for ch in s if ch.isalnum())

        # 左边索引的位置在 0 
        left = 0

        # 右边索引的位置在 len(xArray) - 1
        right = len(xArray) - 1

        # 两个索引向内移动
        # left 向右移动
        # right 向左移动
        while left <= right:
            # 判断这两个元素值是否相同
            if xArray[left] != xArray[right]:
                # 如果不同，直接返回 False
                return  False

            # 否则，left 向右移动
            left += 1
        
            # right 向左移动
            right -= 1
        
        return True

参考代码

class Solution {
public:
    bool isPalindrome(string s) {

        // isalnum() 方法检测字符串是否由字母和数字组成
        // 转换为字符串数组的形式
        string xArray;
        for (char ch : s) {
            if (isalnum(ch)) {
                xArray += tolower(ch);
            }
        }

        // 左边索引的位置在 0 
        int left = 0;

        // 右边索引的位置在 len(xArray) - 1
        int right = xArray.size() - 1;

        // 两个索引向内移动
        // left 向右移动
        // right 向左移动
        while (left <= right) {
            // 判断这两个元素值是否相同
            if (xArray[left] != xArray[right]) {
                // 如果不同，直接返回 false
                return false;
            }

            // 否则，left 向右移动
            left++;

            // right 向左移动
            right--;
        }

        return true;
    }
};