Why the code of valid palindrome is not working for a single edge case?-CodePudding

Below is my code from leetcode. I think that I have write proper logic code but it not work only for edge case - "race a car". It returns true for that but it should be false. why it is? Link of question - https://leetcode.com/problems/valid-palindrome

I know I can find answers with more approaches in solutions section but I want to that what is missing in my code.

class Solution {
public:
    bool isPalindrome(string s) {
        int st =0, e=s.size()-1;
        vector<char> ans1;
        vector<char> ans2;
        while(st<=e){
            
            if((s[st] >= 'a' && s[st] <= 'z') || (s[st] >= 'A' && s[st] <= 'Z') || (s[st] >= '0' && s[st] <= '9')){
                ans1.push_back(islower(s[st]));
                
            }
            if((s[st] >= 'a' && s[st] <= 'z') || (s[st] >= 'A' && s[st] <= 'Z') || (s[st] >= '0' && s[st] <= '9')){
                ans2.push_back(islower(s[e]));
            }

            st  ;
            e--;
        }
        if(ans1 == ans2){return 1;}
        return 0;
    }
};

CodePudding user response：

There are a few issues with the code.

Firstly, the condition (s[st] >= 'a' && s[st] <= 'z') || (s[st] >= 'A' && s[st] <= 'Z') || (s[st] >= '0' && s[st] <= '9') only checks if the character is a letter or a number. This means that other characters, such as spaces and punctuation marks, will be ignored.

Secondly, the code only pushes characters onto the ans1 and ans2 vectors if they are letters or numbers. This means that any spaces or punctuation marks will be ignored, which could lead to incorrect results. For example, the string "A man, a plan, a canal, Panama!" is a palindrome, but your code will not recognize it as such because it ignores the spaces and punctuation marks.

Thirdly, the code is using the islower function to convert the characters to lowercase before adding them to the ans1 and ans2 vectors. However, islower does not actually modify the character - it simply returns true if the character is lowercase, and false otherwise. To actually convert a character to lowercase, you should use the tolower function instead.

Finally, the code is comparing the ans1 and ans2 vectors to determine if the original string is a palindrome. However, this is not a reliable way to check if a string is a palindrome, because the order of the characters in the vectors may not match the order of the characters in the original string. For example, the string "Able was I ere I saw Elba" is a palindrome, but your code will not recognize it as such because the characters in the ans1 and ans2 vectors will be in the opposite order.

To fix these issues, you can modify your code as follows:

Use a regular expression to match only letters and numbers in the input string. This will allow you to ignore any other characters, such as spaces and punctuation marks. Use the tolower function to convert the matched characters to lowercase, so that your code can handle palindromes that have a mixture of uppercase and lowercase letters. Use a single vector to store the matched and converted characters, and compare the characters in this vector to the reversed version of the vector to determine if the original string is a palindrome. This will ensure that the order of the characters is preserved. Here is an example of how your modified code might look:

class Solution {
public:
    bool isPalindrome(string s) {
        // Use a regular expression to match only letters and numbers in the input string
        regex r("[a-zA-Z0-9]");

        // Create a vector to store the matched and converted characters
        vector<char> chars;

        // Iterate over the characters in the input string
        for (char c : s) {
            // If the current character is a letter or number, convert it to lowercase and add it to the vector
            if (regex_match(string(1, c), r)) {
                chars.push_back(tolower(c));
            }
        }

        // Check if the vector is equal to its reversed version
        return chars == vector<char>(chars.rbegin(), chars.rend());
    }

CodePudding user response：

class Solution {
public:
    bool isPalindrome(string s) {
        // Create a vector to store the converted characters
        vector<char> chars;

        // Iterate over the characters in the input string
        for (char c : s) {
            // If the current character is a letter or number, convert it to lowercase and add it to the vector
            if (isalnum(c)) {
                chars.push_back(tolower(c));
            }
        }

        // Check if the vector is equal to its reversed version
        return chars == vector<char>(chars.rbegin(), chars.rend());
    }
}

CodePudding user response：

In the second loop you are using the wrong index, s[st] instead of s[e]! So you are ignoring s[e] if s[st] is not a character or digit.

Your test for characters is not portable anyway, by the way: While C guarantees digits succeeding each other in ascending order this is not necessarily the case for the letters – consider (in-?)famous EBCDIC encoding!

So for testing on letters you should use isalpha function instead and I recommend consistently isdigit for digits. For either of there's isalnum, too, which is what you'd want in your case.

Though be aware that all of these accept an int and char is possibly signed. Characters in extended range (128 - 255) would result in a negative value, so you should cast the input to unsigned char instead.

Then you accept the string by value, so you get a copy of anyway. Then profit from and convert the string to lower in place, ignoring the punctuation marks on the run:

auto pos = s.begin();
for(unsigned char c : s) // explicitly specifying the type performs the necessary cast!
{
    if(isalnum(c))
    {
        // this moves the alnums, already lowered in case, towards
        // front, overwriting the unwanted punctuation marks:
        *pos   = tolower(c);
    }
}
// cut off the remaining ballast, i.e. the places of the moved characters (if any):
s.erase(pos, s.end());

OK, now s contains a string of all lower-case characters (note, though, that there are languages with more than one representation for the same character like Greek 'Σ' (Sigma), with lowercase 'σ' at the beginning or middle and 'ς' at the end of words), which you cannot cover by this approach.

Now you could copy the string, reverse it (std::reverse) and compare reversed copy and original on equality – or you spare this effort by comparing the corresponding characters directly:

for(auto b = s.begin(), e = s.end() - 1; b < e;   b, --e)
{
    if(*b != *e)
    {
        return false;
    }
}
return true;

Note that this would fail on empty string, you might catch this special case right at the beginning (even before converting to lower):

if(s.empty())
{
    return true; // depending on definition, usually empty string does
                 // count as palindrome
}

Actually you could even do all this in one single run; this results, though, in pretty advanced code, which likely goes beyond the scope of this question; if you are still interested in: see at godbolt. Note there especially how copying the string is avoided entirely by accepting it by const reference.