Palindrome String

Question

Code to test if a string is palindrome. The string can contain any number of spaces, punctuations ('.', '?', '!', ','), case sensitive. The code will work for strings like

"madam",
"racecar",
"radar"

But won't work for

"a man a plan a canal panama",
"a    man    a  pla n  a cana L Panama",
"Cigar? Toss it in a can, It is sotragic"

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

int main() {
    char string[100];

    printf("Enter a string: ");
    scanf("%[^\n]", string);

    int isPalindrome = 1;  // assign 0 to this if the string is a NOT palindrome

    // code to test if string is a palindrome
    char str1[100], str2[100];
    int len = strlen(string) - 1;
    int i;

    for (i = 0; i <= len; i++) {
        if (string[i] == '?' || string[i] == '.' || string[i] == '!' || string[i] == ',' || string[i] == '    ') {
            i++; 
        }

        strcpy(str1, string);
    }

    int length = strlen(str1) - 1;
    int j, k;

    for (j = length; j >= 0; j--) {
        str2[j] = str1[len - j]; 
    }

    k = strcmp(str2, str1);

    // at the end you need to test
    if (k == 0) {
        printf("Yes, it is Palindrome!\n");
    } else {
        printf("No, not a Palindrome\n");
    }

    return 0;
}

Answer 1

You need to clean your input string to remove all non-alphabetic characters. You code looks pretty lost on this, but it's a straightforward task of copying over only desired characters (and converting all desired characters to the same case) to a new string.

Be sure to null terminate this new string.

#include <ctype.h>
#incldue <string.h>
#include <stdlib.h>

char *clean_string(const char *str) {
    size_t len = strlen(str);
    char *new_string = calloc(len + 1, 1);

    // Error check `calloc`

    size_t i, j;
    for (i = 0, j = 0; i < len; i++) {
        if (isalpha(str[i])) 
            new_string[j++] = tolower(str[i]);
    }

    new_string[j] = '\0';
    return new_string;
}

If we test this with:

int main(void) {
    char *s = clean_string("a man a plan a CAnal. Panama");
    printf("%s\n", s);
    free(s);
}

We see:

amanaplanacanalpanama

Having solved this problem, your palindrome logic should now be easier. All programming problems are when you break them down into smaller problems.

Answer 2

Although it's possible to map the input to 'all letters' and then do the palindromic comparison, it is not necessary to do so. It is crucial to use the character classification facilities from <ctype.h>. This code won't work on Unicode (UTF-8) data outside the ASCII range, though — it must be a single-byte code set that is used.

This code works on non-degenerate cases:

#include <ctype.h>
#include <stdbool.h>    /* Won't be need in C23 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main(void)
{
    char string[100];
    while (scanf(" %99[^\n]", string) == 1)
    {
        size_t j = strlen(string) - 1;
        size_t i = 0;

        bool is_palindrome = true;
        while (i < j)
        {
            while (!isalpha((unsigned char)string[i]) && i < j)
                i++;
            while (!isalpha((unsigned char)string[j]) && i < j)
                j--;
            if (tolower((unsigned char)string[i]) != tolower((unsigned char)string[j]))
            {
                is_palindrome = false;
                break;
            }
            i++;
            j--;
        }

        printf("The string [%s] %s a palindrome\n", string,
                (is_palindrome ? "is" : "is not"));
    }
    return 0;
}

For example, given the data file:

 madam
 racecar
 radar
 a man a plan a canal panama
 a man a pla n a cana L Panama
 Cigar? Toss it in a can, It is sotragic
 ambivalent
 (    Not=a=palin=drome   )
 (    A=man=a=PlaN=A=Canal===Panama!!!   )
     LeadingBlanksknalbgnidael          

Where there are trailing blanks on the last line, the program above gives the output:

The string [madam] is a palindrome
The string [racecar] is a palindrome
The string [radar] is a palindrome
The string [a man a plan a canal panama] is a palindrome
The string [a man a pla n a cana L Panama] is a palindrome
The string [Cigar? Toss it in a can, It is sotragic] is a palindrome
The string [ambivalent] is not a palindrome
The string [(    Not=a=palin=drome   )] is not a palindrome
The string [(    A=man=a=PlaN=A=Canal===Panama!!!   )] is a palindrome
The string [LeadingBlanksknalbgnidael          ] is a palindrome

I didn't notice until I pasted it that there was at least one leading blank on each line. The %[…] (scan set) conversion specifier — like the %c and %n conversion specifiers, but unlike all other conversion specifiers — does not skip white space. However, on the subsequent lines, I want the code to skip over the newline left behind by the previous input, hence the leading space in the " %99[^\n" format string.

The casts to (unsigned char) are noisy but necessary. The functions declared in <ctype.h> don't work reliably with negative values if the type of plain char is signed (which it is on most machines these days).

C11 §7.4 Character handling <ctype.h> ¶1:

In all cases the argument is an int, the value of which shall be representable as an unsigned char or shall equal the value of the macro EOF. If the argument has any other value, the behavior is undefined.

Another way to deal with this would be to treat the string array as unsigned char by defining unsigned char *str = (unsigned char *)string; and then using str[i] or str[j] where the code currently uses string[i] or string[j], and then the noisy casts in the calls to isalpha() etc would not be necessary any more.

---

As chqrlie rightly pointed out in a comment, the code above does not work correctly when the input is a single letter and any non-zero number of trailing blanks (e.g. [a ]).

The trouble is that the code unconditionally decrements j when j is zero after testing that string[i] equals string[j]. I think the simplest and cleanest fix is to break the loop if i == j before comparing the letters.

This code also creates unsigned char *text = (unsigned char *)string; and then indexes into text to avoid the repeated casts in the calls to isalpha() and tolower().

There is also a mildly interesting question: is a string that contains no letters a palindrome? It hinges on the definition of a palindrome. If it is a sequence of one or more "words" (where a word consists of one or more letters) that reads the same backwards as it does forwards (ignoring the case of the letters and word breaks), then a string that contains no letters is not a palindrome. If you define a palindrome as a sequence of characters where the sequence of letters (ignoring non-letters and the case of the letters) is the same backwards as it is forwards, then a string with no letters is a palindrome. The question doesn't stipulate the required result for a zero-letter string — either result is legitimate. The code assumes that a string devoid of letters is a palindrome.

/* SO 7776-8267 */
#include <assert.h>
#include <ctype.h>
#include <stdbool.h>    /* Won't be need in C23 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main(void)
{
    char string[100];
    while (scanf(" %99[^\n]", string) == 1)
    {
        assert(strlen(string) != 0);
        size_t j = strlen(string) - 1;
        size_t i = 0;
        unsigned char *text = (unsigned char *)string;

        bool is_palindrome = true;
        while (i < j)
        {
            while (i < j && !isalpha(text[i]))
                i++;
            while (i < j && !isalpha(text[j]))
                j--;
            if (i == j)
                break;
            if (tolower(text[i]) != tolower(text[j]))
            {
                is_palindrome = false;
                break;
            }
            i++;
            j--;
        }

        printf("The string [%s] %s a palindrome\n", string,
                (is_palindrome ? "is" : "is not"));
    }
    return 0;
}

It produces the same output on the original test data. It also correctly claims that all but one of these strings are palindromes:

The string [a] is a palindrome
The string [a ] is a palindrome
The string [a  ] is a palindrome
The string [aa] is a palindrome
The string [ab] is not a palindrome
The string [aba] is a palindrome
The string [abXba] is a palindrome
The string [ab=ba] is a palindrome
The string [= ] is a palindrome
The string [=] is a palindrome
The string [@@] is a palindrome
The string [@@@] is a palindrome

Answer 3

There are multiple problems in your code:

• you do not specify the maximum number of characters to store into the destination array for the scanf %s conversion. The program would have undefined behavior if the user enters more than 99 characters on the line. This is a classic software flaw. Use scanf("%99[^\n]", string) to avoid this.

• you do not test the return value of scanf(). If the user hits Enter immediately at the prompt, scanf() will return 0 and leave the string array unchanged, hence unintialized, causing the program to have undefined behavior.

• it is misleading to call len a variable that holds something different from the string length. It is much simpler to define int len = strlen(string); and use a classic iteration for (i = 0; i < len; i++). There is actually no need for a len variable as you can iterate with

    for (i = 0; string[i] != '\0'; i++)
  

• you only test for some punctuation and the test for space is bogus: string[i] == ' ' either uses a multi character character constant, which is a historical oddity that does not do what you want or a '\t' (TAB) if you happen to have a TAB character between the ' in the source code, something to avoid also because it is not readable.

• in the body of the loop, after skipping the separator, you always copy the full source string to str1, defeating the purpose of this loop.

• int length = strlen(str1) - 1; is just as confusing as the previous len definition. Use int length = strlen(str1); and for (j = length; j-- > 0;)

Your question is somewhat confused as you mention the comparison should be case-sensitive but the examples shown as not behaving correctly use different cases (upper and lower case). You should copy the string characters converted to lowercase (or uppercase).

Here is a modified version of your code:

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

int main(void) {
    char string[100];

    printf("Enter a string: ");
    if (scanf("%99[^\n]", string) != 1) {
        fprintf(stderr, "invalid input\n");
        return 1;
    }

    // code to test if string is a palindrome
    char str1[100], str2[100];
    int i, j, k;

    for (i = j = 0; string[i] != '\0'; i++) {
        unsigned char c = string[i];
        if (isalnum(c)) {
            str1[j] = tolower(c);
            j++;
        }
    }
    str1[j] = '\0';  // set the null terminator

    // mirror str1 into str2
    for (i = 0; i < j; i++) {
        str2[i] = str1[j - i - 1]; 
    }
    str2[j] = '\0';  // set the null terminator

    k = strcmp(str2, str1);

    // at the end you need to test
    if (k == 0) {
        printf("Yes, it is Palindrome!\n");
    } else {
        printf("No, not a Palindrome\n");
    }

    return 0;
}

As noted by @Jonathan Leffler, the palindrome test can be performed directly without making copies, hence for a string of arbitrary length. Here is a modified version:

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

// code to test if string is a palindrome:
int isPalidrome(const char *s) {
    size_t i = 0;
    size_t j = strlen(s);

    while (i + 1 < j) {
        unsigned char c1 = s[i++];
        unsigned char c2 = s[--j];
        if (!isalnum(c1)) {
            j++;
        } else
        if (!isalnum(c2)) {
            i--;
        } else
        if (tolower(c1) != tolower(c2)) {
            return 0;
        }
    }
    return 1;
}

int main(void) {
    char string[100];

    printf("Enter a string: ");
    if (scanf("%99[^\n]", string) != 1) {
        fprintf(stderr, "invalid input\n");
        return 1;
    }
    if (isPalindrome(string)) {
       printf("Yes, it is Palindrome!\n");
    } else {
        printf("No, not a Palindrome\n");
    }
    return 0;
}