Algorithm interview Recheck: Validate palindrome strings (bytes)

** Today is the reserve day of xiaohao algorithm “365 brush problem plan”. ** hard to top, I was writing the longest subroutine today. And then ALL of a sudden I was thinking, if I go straight to this and some of you still don’t understand it, why don’t I start with the simplest one. Thus, today’s article was born. So, small hao stayed up until the early morning.

01. Examples of topics

See a small understanding, find a group of data is very interesting, share with you. Leetcode has 993,335 passes for question 1, 396,160 passes for question 2, and 69,508 passes for question 3. Please figure out what I want to say.

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

Example 1:

Input:"A man, a plan, a canal: Panama"Output:true
Copy the code

Example 2:

Input:"race a car"Output:false
Copy the code

02. Illustrated Tutorials

Classic problem, you have to handle it like an inverted string.

First, I want to make sure you know what a palindrome string is. A palindrome string is a string that reads the same forward and backward, such as’ level ‘or’ noon ‘.

Of course, for this case, since the original string contains some unitary elements besides letters and numbers, the first step is to consider replacing it. Because the use of re is really convenient, so direct use of re instead.

//JAVA
s = s.toLowerCase().replaceAll("[^0-9a-z]"."");
Copy the code

If the original string is:

A man, a plan, a canal: Panama
Copy the code

This is what happens after the substitution:

amanaplanacanalpanama
Copy the code

The rest is very simple, we iterate over both characters at the same time, return false if not, and that’s basically what the code looks like (because it’s so simple, I don’t know how to draw….)

//JAVA 
class Solution { 
    public boolean isPalindrome(String s) { 
        s = s.toLowerCase().replaceAll("[^0-9a-z]"."");
        char[] c = s.toCharArray(); 
        int i = 0, j = c.length - 1; 
        while (i < j) { 
            if(c[i] ! = c[j])return false; 
            i++;
            j--;
        }
        return true; }}Copy the code

Execution Result:

And then the above code we must also feel simple a batch. But since we all know which characters are unwieldy (except for letters and numbers), why not just skip through them? So I don’t have to do a substitution preprocessing.

//JAVA
class Solution {
    public boolean isPalindrome(String s) {
        s = s.toLowerCase();
        char[] c = s.toCharArray();
        int i = 0;
        int j = s.length() - 1;
        while(i < j) {
            if(! ((c[i] >='0' && c[i] <= '9') || (c[i] >= 'a' && c[i] <= 'z'))) {
                i++;
                continue;
            }
            if(! ((c[j] >='0' && c[j] <= '9') || (c[j] >= 'a' && c[j] <= 'z'))) {
                j--;
                continue;
            }
            if(c[i] ! = c[j]){return false;
            }
            i++;
            j--;
        }
        return true; }}Copy the code

Execution Result:

Ok, now that we can skip the uninterrupts, is there an API ready to skip the uninterrupts? I looked for it. There was nothing particularly ready-made in Java, but I didn’t want to make wheels, so I looked in another language.

//CPP
class Solution {
public:
    bool isPalindrome(string s) {
        for (int i = 0, j = s.size() - 1; i < j; i++, j--)     
        {
            while (!isalnum(s[i]) && i < j) i++;       
            while (!isalnum(s[j]) && i < j) j--;   
            if (toupper(s[i]) ! =toupper(s[j])) return false;
        }
        return true; }};Copy the code

Note: the isalnum() method checks whether a string consists of letters and numbers. Of course, the C library is also available

But the code still feels very long and uncomfortable. Is there a more concise way to write it? Sacrifice the killer!

//py3
class Solution:
    def isPalindrome(self, s: str) -> bool:
        s = list(filter(str.isalnum, s.lower()))
        return s == s[::- 1] 
Copy the code

And then, I’d like to offer the Battle devil of the Ultimate Killer!

03,

Great oaks from little acorns grow. I hope you are familiar with the judgment of the palindrome string, ready for the following topic ~

That’s the end of today’s topic. Did you learn? Leave your thoughts in the comments section!

I’ve compiled all the problems I’ve written into an e-book, complete with illustrations for each problem. Click to download