Checking if a string is a palindrome

Question

This is the code for checking if a string is a palindrome. The execution time, for sample cases, is 0.40358 seconds. What must be done to increase the performance?

int main(){
    int c,flag = 0;
    char *ch, *h;
    ch = (char *)malloc(sizeof(char)*101);
    h = ch;
    while((c=getchar())!=EOF){
        *ch = c;
        ch++;
    }
    ch--;
    while(ch>=h){
        if(*ch-- != *h++){flag = 1; break;}
    }
    flag == 1?(printf("NO")):(printf("YES"));
}

This is the code with an execution time of 0.4017 seconds for same test cases:

void main()
{
    char a[100],b[1000];
    int n,i,j=0,f=0;
    scanf("%s",a);
    n=strlen(a);
    for(i=n-1;i>=0;i--)
    {
        b[j]=a[i];
        j++;
    }
    for(i=0;i<n-1;i++)
    {
        if(a[i]==b[i])
        {
            f++;

        }
    }
    if(f==n-1)
    {
        printf("YES");
    }
    else
    {
        printf("NO");
    }
}

Why is the former slower than the latter? Are the library functions faster?

Answer 1

The first version is the better approach and as already pointed out, what you measure here is outside the precision of measuring, so performance-wise, these solutions are equal.

Now some suggestions how to improve the code of the first version:

• You allocate your buffer in a needlessly complicated way:

  ch = (char *)malloc(sizeof(char)*101);
  

  first of all, there's no point of casting void * in C, it is implicitly convertible to any data pointer type. Casting it could even hide a bug, see this stackoverflow answer for details. Then, sizeof(char) is defined to be 1, so you can leave it out. The whole line would then look like:

  ch = malloc(101);
  

  But why should you use dynamic allocation at all if you use a fixed size? Just use an array, similar to the code in your second version:

  char buf[101];
  

  Note I also suggest a different name here: buf tells the reader that this is a buffer for something (input in your case), while ch would make you think it's the name of a variable holding a single character.

• You happily overflow your buffer:

  while((c=getchar())!=EOF){
      *ch = c;
      ch++;
  }
  

  You should never write code like this. There are functions for reading a limited amount of data, and as your buffer has a fixed size, you should use such a function, e.g.:

  memset(buf, 0, 101);
  size_t n = fread(buf, 1, 101, stdin);
  char *ch = buf + n;
  

  Without knowing your exact requirements, I guess you didn't intend to analyze "multi-line" palindromes, so using fgets() would be even a better choice:

  if (!(fgets(buf, 101, stdin) && *buf)) exit(1);
  size_t n = strlen(buf);
  if (buf[n-1] == '\n') buf[--n] = 0; // strip newline if present
  char *ch = buf + n;
  

  This is still close to your initial code, in practice, I'd use a larger buffer just to be sure and also define the buffer size as a macro, so I can change it without risking to introduce an overflow bug.

• Regarding your second version, using scanf("%s", ...) will also overflow any buffer. A safe way of using scanf for reading in a fixed size buffer would be scanf("%100s", buf) if buf has a size of 101. I'd suggest not to use scanf() for this purpose at all. -- thanks for the comment!

• A minor point since you are interested in performance:

      flag == 1?(printf("NO")):(printf("YES"));
  

  printf() must scan its first argument to know whether there are more arguments to follow, this is unnecessary for a constant output, so just use puts() if you want an automatic newline or fputs() to avoid the newline. In this case, puts() will be fine:

      flag == 1?(puts("NO")):(puts("YES"));
  

• And as a general advise: Try to find better variable names that really describe the meaning of the variable, like instead of a flag, how about a isPalindrome?

Suggested improved version which also improves on readability:

#include <stdio.h>
#include <string.h>

#define BUFSIZE 1024
char buf[BUFSIZE]; // 1K buffer with static storage

int main(void)
{
    if (!(fgets(buf, BUFSIZE, stdin) && *buf))
    {
        // reading a line from stdin failed, give up
        return 1;
    }

    size_t n = strlen(buf);
    if (buf[n-1] == '\n') buf[--n] = 0; // strip newline

    char *front = buf;
    char *back = buf + n;

    int isPalindrome = 1;
    while (back > front)
    {
        if (*--back != *front++)
        {
            isPalindrome = 0;
            break;
        }
    }

    puts(isPalindrome ? "YES" : "NO");
    return 0;
}

Answer 2

You can't really call a difference of 1% slower or faster. You should consider that both codes have exactly the same performance.

The only explanation for a speed difference between those two applications comes from the malloc (which is slightly slower than an array).

IMO, first code is better than second; the second one is quite hard to get (you are basically reversing a string, then comparing the reversed string with the normal one). I actually had to read the code 3 times to understand what was done.

About code review in itself:

• First code sample:

  You should indent your code in a consistent manner.

  int c,flag = 0;
  char *ch, *h;
  

  Those variables are poorly named; flag could be replaced by is_palindromic, h could be string_start/str_start/str, and ch string_from_end/string_reverse etc....

  while((c=getchar())!=EOF){
  

  It's usually a good idea to separate comparators and equal sign from their operands, so it'd be something like this:

  while((c = getchar()) != EOF){
  

• Second code sample:

  char a[100],b[1000];
  int n,i,j=0,f=0;
  

  Same as before, you should also avoid declaring 4 variables on the same line (especially considering you have both initialized and non-initialized variables).

Answer 3

You are comparing all the characters of two the arrays:

for(i=0;i<n-1;i++)
{
    if(a[i]==b[i])
    {
        f++;

    }
}

Instead, you can do something like this :

isPalin = 0 ;
n= strlen(charArray)
for(i=0;i<n/2;i++)
{
    if( charArray[i] != charArray[j] )
    {
        isPalin = 1 ; 
        break ;
    }
    j-- ;
}
puts(isPalin? "YES" : "NO" ) ; 

You only use one array and only traverse till (n/2-1) position of the array compared to your example. Execution time comes down to 0.822 secs.