LeetCode.125 验证回文串

题目描述：

原题地址

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

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

示例一

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

示例二

输入: "race a car"
输出: false
解释： "raceacar" 不是回文串

提示

• 1<=s.length<=2∗1051 <= s.length <= 2 * 10^51<=s.length<=2∗105
• 字符串 s 由 ASCII 字符组成

思路分析

反转比较

题目中说只考虑字母和数字，但是示例一中包含了其他的字符，所以我们首先要把数字和字母过滤出来，然后全部转小写或大写，转完之后直接使用reverse反转一下字符串，再和原字符串对比一下就得到答案了。

利用kotlin的特性的话，代码可以很精简。

AC代码

class Solution {
    fun isPalindrome(s: String): Boolean =
        s.toLowerCase().toCharArray().filter { it in 'a'..'z' || it in '0'..'9' }
            .let { it.reversed() == it }
}

class Solution {
    fun isPalindrome(s: String): Boolean =
        s.toLowerCase().toCharArray().filter { it.isLetterOrDigit() }
            .let { it.reversed() == it }
}

双指针法

这个思路也很简单，定义两个指针，一个从左边向右遍历，一个从右向左遍历，注意指针指向的是下一个正确的位置，也就是要注意过滤非数字和字母以及忽略大小写，当遇到不相等的时候说明这个字符串不是回文串。

总结

AC代码

class Solution {
    fun isPalindrome(s: String): Boolean {
        var i = 0
        var j = s.length -1
        while (i < j) {
            while (!Character.isLetterOrDigit(s[i]) && i < j) {
                i++
            }
            while (!Character.isLetterOrDigit(s[j]) && i < j) {
                j--
            }
            
            if (Character.toLowerCase(s[i]) != Character.toLowerCase(s[j])) {
                return false
            }
            
            i++
            j--
        }
        return true
    }
}

总结

这题的确简单，两个方法都是一遍过。

参考

验证回文串 - 验证回文串 - 力扣（LeetCode） (leetcode-cn.com)

Kotlin特性解法 - 验证回文串 - 力扣（LeetCode） (leetcode-cn.com)

125. 验证回文串 题解 - 力扣（LeetCode） (leetcode-cn.com)