How to remove spaces and check if a string is a palindrome?

Question

I am trying to figure out how to remove spaces, and then check if the string with the removed spaces is a palindrome.

I have tried both things separately, and I can't get them to work together though.

int check_palindrome(char *);

int main()
{
    char s1[20];
    printf("Enter the string...\n");
    gets(s1);

    int x;
    x=check_palindrome(s1);
    x?printf("%s = is a Palindrome\n", s1):printf("%s = is Not a Palindrome\n", s1);
}

int check_palindrome(char *s)
{
    int i,j;
    for(i=0;s[i];i++);

    for(i=i-1,j=0;i>j;i--,j++)
    {
        if(s[i]!=s[j])
        {
            return 0;
        }
    }
    if(s[i]==s[j])
    {
        return 1;
    }
}

This code works for checking a palindrome, but it doesn't work if the input starts with a capital letter, or if it has spaces. e.g i expect the output of 'nurses run' to be 'nurses run is a palindrome', but the actual output is 'nurses run is not a palindrome', because of the space in between, and the expected output of 'Dad' is 'Dad is a palindrome', but it returns 'Dad is not a palindrome'.

Answer 1

I love your concise style. So the answer has to fit.

1.) the capital letter reverse the logic:

if(s[i]==s[j]) 
continue;
if(s[i]==s[j]+DIFF_a_A) continue;
if(s[i]+DIFF_a_A==s[j]) continue;
return false;

with #define DIFF_a_A ('A' - 'a')

2.) the blanks put the increments into the loop:

for(i=i-1,j=0;i>j;){
    if(s[i] == ' ') i--, continue;
    if(s[j] == ' ') j++, continue;
        ...
    i--,j++;
}

Does this fit your style?

Answer 2

How to remove spaces and check if a string is a palindrome?

There are two-parts to your question: (1) "How to remove spaces"? and (2) [How to] "check if a string is a palindrome?". You should approach the problem in two discrete steps.

Removing whitespace from a string can be done in one of two different ways, (1) remove spaces in-place in the original string (presuming your original is a mutable string and not a String Literal) or (2) remove spaces while filling a second string with the non-whitespace characters from the first, preserving the first string unchanged (works regardless of whether the original is mutable). Your safest choice is the latter.

A simple function that provides the source and destination buffers as parameters to the function to remove whitespace could be as simple as:

void removespace (char *dest, const char *src)
{
    size_t n = 0;
    while (*src) {
        if (!isspace(*src))
            dest[n++] = *src;
        src++;
    }
    dest[n] = *src;     /* nul-terminate */
}

Moving to the second part of your problem, if you are having problems wrapping your head around using a start and end pointer to iterate from the ends of the string to the middle to check if the string is a palindrome, you can do the same thing with string indexes. Also, whenever you need to check whether something is whitespace or convert between character case, use the macros isspace() or tolower() / toupper() provided in ctype.h. (otherwise YOU are responsible for ALL the conditional checks required)

A simple checkpalindrome() implementation using string indexes could be:

int checkpalindrome (const char *s)
{
    size_t n = 0, len = strlen (s);

    while (len-- > n)   /* loop over each start/end lowercase char */
        if (tolower (s[n++]) != tolower (s[len]))
            return 0;

    return 1;
}

Now on your implementation of main() reading your string from the user Never, ever, ever use gets(). It is so insecure and so prone to exploit by buffer-overrun it has been removed from the standard library in C11. See Why gets() is so dangerous it should never be used!. Just use fgets() instead and trim the line-ending from the buffer filled by fgets by overwriting the line-ending with the nul-terminating character. (strcspn() is convenient for this).

Putting it altogether (and using your ternary to control the "is" or "is not" output) you could do:

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

#define MAXC 1024   /* if you need a constant, define one (or more) */

void removespace (char *dest, const char *src)
{
    size_t n = 0;
    while (*src) {
        if (!isspace(*src))
            dest[n++] = *src;
        src++;
    }
    dest[n] = *src;     /* nul-terminate */
}

int checkpalindrome (const char *s)
{
    size_t n = 0, len = strlen (s);

    while (len-- > n)   /* loop over each start/end lowercase char */
        if (tolower (s[n++]) != tolower (s[len]))
            return 0;

    return 1;
}

int main (void) {

    char s[MAXC], nospace[MAXC];

    fputs ("enter a string: ", stdout);
    if (!fgets (s, MAXC, stdin)) {  /* Never, Ever use gets() */
        fputs ("(user canceled input)\n", stderr);
        return 1;
    }
    s[strcspn (s, "\r\n")] = 0; /* trim line-ending */
    removespace (nospace, s);   /* remove whitespace from s */

    printf ("'%s' => %s a palindrome.\n",
            s, checkpalindrome (nospace) ? "is" : "is not");

    return 0;
}

(note: Never Skimp on Buffer Size!)

Example Use/Output

$ ./bin/checkpalindrome
enter a string: a
'a' => is a palindrome.

(you can change how you handle a single character string to fit your needs)

$ ./bin/checkpalindrome
enter a string: aa
'aa' => is a palindrome.

$ ./bin/checkpalindrome
enter a string: ab
'ab' => is not a palindrome.

$ ./bin/checkpalindrome
enter a string: aba
'aba' => is a palindrome.

$ ./bin/checkpalindrome
enter a string: abc
'abc' => is not a palindrome.

$ ./bin/checkpalindrome
enter a string: A man a plan a canal Panama
'A man a plan a canal Panama' => is a palindrome.

Look things over and let me know if you have questions.

Answer 3

If you do not need the modified string you can save a lot of work and simply ignore whitespace and case in your comparison, for example like that:

int ispalindrome = 1;
while (s < e && ispalindrome) {
        while (*s == ' ') s++;
        while (*e == ' ') e--;
        if (tolower(*s++) != tolower(*e--))
                ispalindrome = 0;
}

with s pointing to the start and e pointing to the end (last character) of the string.

Edit:

I just realized, that there is a corner case where an out of bounds array access can happen, if the whole string only consists of spaces. Then the second space-skip-loop will go past the "left" end of the array. So change this to

        while (*e == ' ' && e > s) e--;

Note that in this case, ispalindrome will be false. It is a matter of definition if the empty string is a palindrome or not.

Answer 4

I would start by formatting the string to make it easier to analyze by removing all special/whitespace characters, and then converting all letters to upper or lower case.