Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.

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.

  • Example 1:

    Input: “A man, A plan, A canal: Panama” Output: true explanation: “Amanaplanacanalpanama” is A palindrome

  • Example 2:

    Input: “raceacar” Output: false Explanation: “raceacar” is not a palindrome

Source: force buckle

[Double pointer method]

// C++
class Solution
{
public:
    bool isPalindrome(string s)
    {
        // Returns true if the string is empty
        if (s.empty())
        {
            return true;
        }
        
        // Define the left and right Pointers
        int left = 0;
        int right = s.size() - 1;
        
        // The left pointer is smaller than the right pointer
        while (left <= right)
        {

            char tmpLeft = s[left];
            char tmpRight = s[right];
            // Check whether the left and right Pointers point to characters between [A and Z]
            // If it is between [a-z], convert it to [a-z].
            if (tmpLeft >= 'A' && tmpLeft <= 'Z')
            {
                tmpLeft += 32;
            }
            if (tmpRight >= 'A' && tmpRight <= 'Z')
            {
                tmpRight += 32;
            }

            // Check whether the left and right Pointers point to characters between [a-z][0-9]
            if ((tmpLeft >= 'a' && tmpLeft <= 'z') || (tmpLeft >= '0' && tmpLeft <= '9'))
            {
                // If the left and right Pointers are between [a-z][0-9], the two characters are equal
                if ((tmpRight >= 'a' && tmpRight <= 'z') || (tmpRight >= '0' && tmpRight <= '9'))
                {
                    Return false if the left and right characters are not equal
                    if(tmpLeft ! = tmpRight) {return false;
                    }
                    // The left and right Pointers are incremented and subtracted by 1
                    left++;
                    right--;
                }
                else{ right--; }}else{ left++; }}return true; }};Copy the code

【 Container attribute method 】

// C++
// Use the reverse method of the list container to determine if the string is a palindrome
bool isPalindrome2(string s)
{
    list<char> L1;
    // Convert characters to lowercase and add them to the list container
    string::iterator it = s.begin(a);while(it ! = s.end())
    {
        if (*it >= 'A' && *it <= 'Z')
        {
            L1.push_back(*it + 32);
        }
        else if ((*it >= 'a' && *it <= 'z') || (*it >= '0' && *it <= '9'))
        {
            L1.push_back(*it);
        }
        it++;
    }
    // The list copy constructor assigns the value of L1 to L2
    list<char> L2(L1);
    // reverse L2
    L2.reverse(a);// if L2 reverses to L1, it is a palindrome string
    if (L2 == L1)
    {
        return true;
    }
    return false;
}
Copy the code

List is a discontinuous storage structure on a physical storage unit. The logical order of data elements is realized by connecting Pointers in the list. The storage mode of the list is not continuous memory space. Linked lists are more flexible to use, but the extra cost of space and time is high.