Palindrome Checker Algorithm

Question

Here is how I solved this problem (though this is not the only nor the best way by any means) for an assignment where it was also requisite to determine if a string was a reverse prefix of the other.

Obviously a palindrome is a reverse prefix of itself so if you can determine a reverse prefix then you can determine a palindrome.

I would love some feedback on my code as well as any thoughts on my implementation/solution.

int main()
{
    char string1[50];
    char string2[50];
    
    printf("Please enter a string: ");
    gets(string1);
    if (strlen(string1) == 1)
        exit(1);
    printf("Please enter a second string: ");
    gets(string2);
    printf("\nString 1 = %s", string1);
    printf("\nString 2 = %s\n", string2);
    if (isReversePrefix(string1, string2))
        printf("String 2 is a reversed prefix of string 1\n");
    if (isPalindrome(string1))
        printf("String 1 is a palindrome\n");
    else
        printf("String 1 is not a palindrome\n");
    if (isPalindrome(string2))
        printf("String 2 is a palindrome\n");
    else
        printf("String 2 is not a palindrome\n");
    return 0;
}
/************************************************
 isReversePrefix - Receives two string pointers
 and determines if the second is a reverse
 prefix of the first. Returns either true or
 false.
 The word 'HIM' has the following prefixes 'H', 'HI',
 'HIM'. All of these can be reversed to 'H', 'IH', 'MIH'
 ************************************************/
int isReversePrefix(char *str1, char *str2)
{
    char *temp1 = str1;
    char *temp2 = str2;
    
    if (strlen(str2) > strlen(str1))
        return 0;
    
    strrev(temp2);
    while ((*temp1 == *temp2) && (*temp2 != '\0'))
    {
        temp1++;
        temp2++;
    }
    if (*temp2 == '\0')
        return 1;
    else
        return 0;
}
/************************************************
 isPalindrome - receives one string parameter and 
 checks if it is a palindrome or not. Returns
 true if it is and false if not.
************************************************/
int isPalindrome(char *str1)
{
    char *start = str1;
    char *end = str1 + strlen(str1) - 1;
    if (isReversePrefix(start, end))
        return 1;
    else
        return 0;
}

Answer 1

• Since the char array sizes are fixed, you should make sure the inputs are of an appropriate size before continuing. This should best be done with the function doing the reading.

  Very important: gets() is unsafe as it has no knowledge of buffer size thus is vulnerable to buffer overflow. Instead, use fgets(), which is safer as it takes a buffer size as an argument.

• Consider hard-coding the 50 to make its intent clear.

  #define MAX_LENGTH 50
  

• Since you're already in main(), you can use return 1 instead of exit(1).

• Unformatted strings like this:

  printf("Please enter a string: ");
  

  can instead be output using puts():

  puts("Please enter a string: ");
  

  Be aware that puts() automatically appends a newline at the end. If you don't want this newline, then you can use fputs() instead:

  fputs("Please enter a string: ", stdout);
  

Answer 2

1. These functions should be able to handle constant arrays.

   // int isReversePrefix(char *str1, char *str2)
   int isReversePrefix(const char *str1, const char *str2)
   

2. By calling strlen(str2) > strlen(str1), code is marching down each string twice. Only need to find the end of one.

   int isReversePrefix(const char *str1, const char *str2) {
     const char *p2 = str2[strlen(str2)];
   
     while (*str1 && p2 > str2) {
       p2--;
       if (*str1 != *p2) {
         return 0;
       }
       str1++; 
     }
   
     return *str1 == '\0' && p2 == str2;
   }
   

3. Now that isReversePrefix() handles constant strings, isPalindrome() is easy:

   int isPalindrome(char *str1) {
     return isReversePrefix(str1, str1);
   }
   

4. Original isPalindrome() has 2 problems: Consider what happens when str1 == ""

   char *end = str1 + strlen(str1) - 1;
   if (isReversePrefix(start, end))
   

5. Calling isReversePrefix() with isReversePrefix(start, end) simple will not work. The code is only checking if the first char of the string matches its end.

6. Original isReversePrefix() reverses the contents of str2. This may be an very unhappy side effect for an application calling isReversePrefix()

7. An efficient re-write of isPalindrome() would find the length and then do length/2 compares.

Answer 3

Two issues which have not been identified about this function.

int isPalindrome(char *str1)
{
    char *start = str1;
    char *end = str1 + strlen(str1) - 1;
    if (isReversePrefix(start, end))
        return 1;
    else
        return 0;
}

You can include <stdbool.h> and then have this be the following. The same could be applied to isReversePrefix.

bool isPalindrome(char *str1)
{
    char *start = str1;
    char *end = str1 + strlen(str1) - 1;
    if (isReversePrefix(start, end))
        return true;
    else
        return false;
}

But the conditional at the end is totally unnecessary. You already have a boolean, you don't need to convert it to a boolean.

bool isPalindrome(char *str1)
{
    char *start = str1;
    char *end = str1 + strlen(str1) - 1;

    return isReversePrefix(start, end);
}