0

I was wondering if I am writing correct "isalnum" logic. This program is checking if the string is a palindrome or not and when I input the string "race a car", it keeps saying it is true, i.e. it's a palindrome.

bool isPalindrome(string s) {
  for (int i = 0, j = s.size() - 1; i < j; i++, j--) {
    while ((s[i] < 'a' || s[i] > 'z') && (i < j) ||
           (s[i] < 'A' || s[i] > 'Z') && (i < j) ||
           (s[i] < '0' || s[i] > '9') && (i < j))
      i++;
    while ((s[j] < 'a' || s[j] > 'z') && (i < j) ||
           (s[j] < 'A' || s[j] > 'Z') && (i < j) ||
           (s[j] < '0' || s[j] > '9') && (i < j))
      j--;
    if (toupper(s[i]) != toupper(s[j])) return false;
  }
  return true;
}
4
  • 3
    Why not simply use std::isalnum? Jan 6, 2021 at 18:05
  • Why don't you use isalnum while using toupper?
    – MikeCAT
    Jan 6, 2021 at 18:06
  • 2
    why not reverse the string, and compare to the original for equality? Jan 6, 2021 at 18:06
  • @SamVarshavchik Also non-alnum characters should be removed from the string for checking.
    – MikeCAT
    Jan 6, 2021 at 18:07

2 Answers 2

1

No, your logic is not correct, well, at least not for all the character sets that C++ can use. In ASCII, the letters of the alphabet are in contiguous blocks, so something like

(s[i]<'A'||s[i]>'Z')

works just fine. The issue with that is that ASCII isn't the only character set C++ supports. The most common example to counterpoint ASCII is EBCDIC which has the characters {, }, and \ in between A and Z.


One thing that is guaranteed though is that 0 through 9 are contiguous in all character sets that C++ supports so it's always legal to text if a character is a number using

if (char_var >= '0' && char_var <= '9')
1
  • My upvote for mentioning EBCDIC. Not that I ever saw it in my daily business but the memory to such strange things of CS history must be kept alive... Jan 6, 2021 at 18:34
1

Assuming contiguous alphabets (which isn't going to hold in reality), your logic is broken by the fact that you're doing multi-range checking, where disqualification in one range is still qualified in another.

Specifically, this:

while((s[i]<'a'||s[i]>'z')&&(i<j)||(s[i]<'A'||s[i]>'Z')&&(i<j)||(s[i]<'0'||s[i]>'9')&&(i<j))i++;

Now, consider this: suppose a[i] is in 'a'..'z', so the first range check will be false. But, if that's the case then it is NOT in 'A'..'Z' and is certainly not in '0'..'9'. Since both of those tests result in true, the loop advances i and continues on. As your loop is written, so long as the character is not in at least one of those ranges the loop continues. Since the ranges are mutually exclusive, there will ALWAYS be at least one the current character is not within. That OR separating condition is wrong. It shouldn't be not-in one of those ranges; it should be not-in ALL of those ranges. Thus.. AND is appropriate.

Short work with a debugger will tell you the very first pass of your outer-for-loop is advancing i all the way to j. The second loop is skipped because j and i are already equal, and since s[i] == s[j] is definitely true when i == j, the result is true.

Short version: your loop conditions are broken, even on contiguous character sequence platforms.

The loop you're more inclined to succeed with would be something like:

while( (i < j) && (s[i]<'a'|| s[i]>'z') && (s[i]<'A'||s[i]>'Z') && (s[i]<'0'||s[i]>'9') ) 
    i++;

I leave the other loop and consideration for not doing any of this because of encodings where it will not work as an exercise for you.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.