Practical 6(b): Is This String a Palindrome?

madam    palindrome
level    palindrome
abba     palindrome
mumbai   not a palindrome
a        palindrome
(empty)  palindrome

The last two rows are the edge cases an examiner reaches for, and both come out as palindromes.

A single character: i is 0 and j is 0, so i < j is false, the loop never runs, and the flag is still 1. That is the right answer, and the program gets it without a special case.

The empty string: strlen("") is 0, so j is minus 1, i < j is false at once, and the answer is again yes. This one is a convention rather than a discovery. A string with no characters reads the same in both directions because there is nothing to read, so it is a palindrome vacuously, in the same way that 0! is 1. If your examiner wants an empty input refused instead, that is one if before the loop; what matters is that you know which answer your program gives and why.

Spaces and capital letters: the decision this chapter makes

Is Madam a palindrome? Compared exactly, no: M and m are different characters, because a capital M is 77 and a small m is 109. Is nurses run a palindrome? Compared exactly, no, because of the space.

There is no single right answer, and a student who has not decided will be caught out.

This book compares exactly, as typed. That is what MU's wording asks for: the given string, as given. A program that silently strips spaces is answering a different question from the one it was asked.

But the other version is two if statements away, and it is worth knowing:

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

int main(void)
{
    char s[] = "Madam, I'm Adam";
    int i = 0, j = (int) strlen(s) - 1, flag = 1;

    while (i < j) {
        if (!isalpha((unsigned char) s[i])) { i++; continue; }
        if (!isalpha((unsigned char) s[j])) { j--; continue; }

        if (tolower((unsigned char) s[i]) != tolower((unsigned char) s[j])) {
            flag = 0;
            break;
        }
        i++;
        j--;
    }

    printf("\"%s\" is %sa palindrome when letters alone are compared\n",
           s, flag ? "" : "not ");

    return 0;
}

"Madam, I'm Adam" is a palindrome when letters alone are compared

isalpha and tolower come from ctype.h. The cast to unsigned char is not decoration: those functions are defined for values of an unsigned char and for the end-of-file marker, and passing a plain char that happens to be negative is undefined behaviour. It costs nothing and it is correct.

The number palindrome, which is a different program

An examiner may ask for a palindrome number rather than a string. That is not this program with %d: it is the reverse-digits loop from [Practical 3(a): Reversing the Digits of a Number] followed by one comparison.

reverse the digits of n into rev
if (rev == original) it is a palindrome

Both are worth having in the journal, because the two questions sound identical and the programs share nothing.

What beginners get wrong

Setting j to strlen(s). That subscript holds the null character, so the first comparison is against '\0' and every string comes out as not a palindrome.

Looping while i <= j. At the middle character of an odd-length word it compares that character with itself, which is harmless but wasteful, and on an even-length word it compares a pair that has already been compared.

Comparing the whole string with its reverse using ==. In C, == on two arrays compares addresses, not contents, and two different arrays never have the same address. Use strcmp, which is [Practical 6(c): strlen and strcmp].

Forgetting to reset the flag between two tests when the program checks several strings in one run.

Assuming Madam is a palindrome. Not when compared exactly. Decide, and say so.

Quick revision

• A palindrome reads the same forwards and backwards.
• Two subscripts: i from 0, j from strlen(s) - 1, loop while i < j.
• Compare s[i] with s[j], then i++ and j--.
• One mismatch settles it; leave the loop at once.
• strlen(s) - 1 is the last character; strlen(s) is the null.
• A single character is a palindrome.
• Capitals and spaces matter unless you deliberately ignore them with tolower and isalpha from ctype.h.
• A palindrome number is the reverse-digits loop plus one comparison, not this program.

What goes in your journal

Aim, the nine-step algorithm, a flowchart with the loop and the mismatch decision, the program, and two runs: one palindrome and one that is not. Write the walking table for your own word, three or four rows of i, j and the two characters. In the conclusion state what your program does about capitals and spaces; that is the question you will be asked.

Test yourself

1. Why is j set to strlen(s) - 1? Because strlen counts the characters and the subscripts start at 0, so the last character sits one place before the count. strlen(s) is the subscript of the terminating null.

2. Why i < j rather than i <= j? Because when i and j meet, that character is the middle one and comparing it with itself proves nothing. All the pairs have already been checked.

3. Is Madam a palindrome? Not when the characters are compared exactly, because a capital M and a small m are different characters. It is if the comparison is made case insensitive with tolower.

4. How many comparisons does a word of ten characters need? Five. Each comparison settles a pair, and ten characters make five pairs.

5. Why can you not test s == reverse with ==? Because == on arrays compares their addresses, which are always different for two separate arrays. Contents are compared with strcmp.

6. How would you check whether a number is a palindrome? Reverse its digits with the loop from the reversing practical, and compare the reversed value with a saved copy of the original.