Leetcode 0125. validate palindrome string

【LetMeFly】125. Verify the palindrome string

Force button topic link ：https://leetcode.cn/problems/valid-palindrome/

Given a string , Verify that it is a palindrome string , Consider only alphabetic and numeric characters , The case of letters can be ignored .

explain ： In this question , We define an empty string as a valid palindrome string .

 

Example 1:

 Input : "A man, a plan, a canal: Panama"
 Output : true
 explain ："amanaplanacanalpanama"  It's a palindrome string 

Example 2:

 Input : "race a car"
 Output : false
 explain ："raceacar"  It's not a palindrome string 

 

Tips ：

• 1 <= s.length <= 2 * 105
• character string s from ASCII Character composition

Method 1 ： Clean string + Judge

This method is easy to think of , But the space complexity is slightly larger

Since the topic says only Alphanumeric , Then why don't we extract the alphanumeric , Form a new string .

string strip(string& s) {
    
    string ans;
    for (char& c : s) {
    
        if (c >= 'a' && c <= 'z')
            ans += c;
        else if (c >= 'A' && c <= 'Z')  //  The words of capital letters will be converted into lowercase （ This question is not case sensitive ）
            ans += (char)(c + 32);
        else if (c >= '0' && c <= '9')
            ans += c;
    }
    return ans;
}

after , Then judge whether the cleaned string is a palindrome string （ From front to back, the variable is half a character , Look at number $i$ One and last $i$ Whether the characters are the same ）

bool isPalindrome(string& s) {
    
    s = strip(s);
    int n = s.size();
    for (int i = 0; i < n / 2; i++) {
    
        if (s[i] != s[n - i - 1])
            return false;
    }
    return true;
}

• Time complexity $O(N)$, among $N$ Is the length of the string
• Spatial complexity $O(N)$

AC Code

C++

class Solution {
    
private:
    string strip(string& s) {
    
        string ans;
        for (char& c : s) {
    
            if (c >= 'a' && c <= 'z')
                ans += c;
            else if (c >= 'A' && c <= 'Z')
                ans += (char)(c + 32);
            else if (c >= '0' && c <= '9')
                ans += c;
        }
        return ans;
    }
public:
    bool isPalindrome(string& s) {
    
        s = strip(s);
        int n = s.size();
        for (int i = 0; i < n / 2; i++) {
    
            if (s[i] != s[n - i - 1])
                return false;
        }
        return true;
    }
};

Method 2 ： No extra space , Ignore non alphanumeric characters directly

In this way, it is impossible to directly determine the first $i$ The penultimate number corresponding to an alphanumeric $i$ Who are the first alphanumeric .

Then use double pointers directly , One before and one after , One goes back and forth , Ignore when encountering non alphanumeric , Until the front and back pointers overlap

• Time complexity $O(N)$, among $N$ Is the length of the string
• Spatial complexity $O(1)$

AC Code

C++

class Solution {
    
private:
    inline bool isCN(char c) {
    
        if (c >= 'A' && c <= 'Z')
            return true;
        if (c >= 'a' && c <= 'z')
            return true;
        if (c >= '0' && c <= '9')
            return true;
        return false;
    }
public:
    bool isPalindrome(string s) {
    
        int l = 0, r = s.size() - 1;
        while (l < r) {
    
            //  Find the next alphanumeric 
            while (!isCN(s[l]) && l < r)
                l++;
            while (!isCN(s[r]) && l < r)
                r--;
            //  Alphabetic words are uniformly converted to lowercase 
            if (s[l] >= 'A' && s[l] <= 'Z')
                s[l] += 32;
            if (s[r] >= 'A' && s[r] <= 'Z')
                s[r] += 32;
            printf("l = %d, r = %d, s[%d] = %c, s[%d] = %c\n", l, r, l, s[l], r, s[r]);  //**********
            if (s[l] != s[r])
                return false;
            l++, r--;
        }
        return true;
    }
};

Synchronous posting on CSDN, Originality is not easy. , Reprint please attach Link to the original text Oh ~
Tisfy：https://letmefly.blog.csdn.net/article/details/125889961