Another way to check palindromes

By these days, I was scrolling into Linkedin and Twitter, and see a very common coding challenge: check if a string is a palindrome.

It's a very simple challenge. A palindrome is a word or phrase that can be read the same inwards and backwards. Just like:

• tesset
• mam
• biaib

and so on.

But the general approach people follow is like this:

In other words, they take the original string and then reverse it, then compare it against the original.
It's a very valid approach, but I want to sugest a clever approach for it.

See that you need to produce a new allocation for the string, then compare char by char. The way it can be more challenging is, how to do it using a O(1) more memory, and making less comparisons?

Let me explain this better.

The better approach to tackle this problem is by using two-pointer approach.

A string is nothing more than a char array, and we can go through it char by char, and make traversals and comparisons against any char of the array.

Let's refactor it using the new approach using two pointer.
The first thing we need to made is to take a rune slice from it:

  r := []rune(str);

Strings in Go are readonly, so basically, the string is immutable and cannot be changed. The rune slice, otherwise can be changed, and then, the conversion between the two make a copy of string bytes, but then, we are not make another copy here, because we will continue in the same stack frame, and we don't gonna produce a new string.

After that, we gonna start the loop, with a pointer in the start of the rune and another from the end, and we gonna traverse it until one crosses another. We gonna make the comparisons here:

func isPalindrome(str string) bool {
    r := []rune(str)
    for i, j := 0, len(r)-1; i < j; i, j = i+1, j-1 {
        if r[i] != r[j] {
            return false
        }
    }
    return true
}

That way, if the comparisons goes ok, and all the chars are the same, then it's a palindrome. Otherwise, it returns false instantly.

The above is the detailed content of Another way to check palindromes. For more information, please follow other related articles on the PHP Chinese website!