Leetcode.125 validates palindrome strings

This is the first day of my participation in the August Text Challenge.More challenges in August

Title description:

The original address

Given a string, verify that it is a palindrome string, considering only alphanumeric characters, regardless of letter case.

Note: In this case, we define an empty string as a valid palindrome string.

The sample a

Input: "A man, A plan, A canal: Panama" Output: true explanation: "Amanaplanacanalpanama" is A palindromeCopy the code

Example 2

Input: "raceacar" Output: false Explanation: "raceacar" is not a palindromeCopy the code

prompt

• 
  $1 <= s.length <= 2 * 10^5$
• stringsConsists of ASCII characters

Thought analysis

Reverse comparison

The question says that only letters and numbers are considered, but example 1 contains other characters, so we need to filter out the letters and numbers first, then change all lowercase or uppercase characters, and then use reverse to reverse the string and compare it with the original string to get the answer.

With Kotlin’s features, the code can be minimal.

AC code

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

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

Double pointer method

Define two Pointers, one traversing from left to right and one traversing from right to left, and note that the pointer points to the next correct position. Filter non-numbers and letters and ignore case.

conclusion

AC code

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}}Copy the code

conclusion

This is really easy. I’m going to do it both ways.

reference

Validation palindrome string – Validation Palindrome String – LeetCode (leetcode-cn.com)

Kotlin feature Solution – Validation palindrome String – Force link (LeetCode) (leetcode-cn.com)

125. Verifying palindrome string problem solving – LeetCode (leetcode-cn.com)