Tests for palindromes in C and C++

Question

A question I've been asked on interactive phone screens is to code a test to determine whether a string is a palindrome or not. I am providing two examples here: one in C and one in C++. They both work and they both compile without errors or warnings. I believe my C example is good, with the possible exception of variable names (some of you may not like the register char* declarations, but they are valid in C).

My goal was an \$O(n)\$ solution with out reversing the string.

My question is about the C++ version, and I miss using iterators. Is there a way to make this more C++ like?

I can think in C; I can't necessarily think in C++.

Palindrome checker in C

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

bool palindromeChecker(char *possiblePalindrome)
{
    bool isPalindrome = true;
    size_t length = strlen(possiblePalindrome);

    if (length < 3)
    {
        isPalindrome = false;
    }
    else
    {
        register char *leftSide = possiblePalindrome;
        register char *rightSide = &possiblePalindrome[length-1];

        while ((leftSide < rightSide) && isPalindrome)
        {
            if (*leftSide != *rightSide)
            {
                isPalindrome = false;
            }
            leftSide++;
            --rightSide;
        }
    }

    return isPalindrome;
}

int main(int argc, const char * argv[]) {
    char testString[BUFSIZ];
    bool iSPalendrome;

    printf("Enter a test string to be checked for if it is a palindrome\n");
    scanf("%s", testString);
    iSPalendrome = palindromeChecker(testString);
    printf("The test string %s is %s a palindrome\n", testString, (iSPalendrome? "" : "Not"));

}

Palindrome checker in C++

#include <iostream>
#include <string>

bool IsPalindrome(std::string PossiblePalindrome)
{
    bool Palidrime = true;

    if (PossiblePalindrome.size() < 3)
    {
        Palidrime = false;
    }
    else
    {
        std::string::iterator leftSide = PossiblePalindrome.begin();
        std::string::iterator rightSide = PossiblePalindrome.end();
        rightSide--; // end is past the end of the possible palindrome so decrement to point to a character.

        while ((leftSide < rightSide) && Palidrime)
        {
            if (*leftSide != *rightSide)
            {
                Palidrime = false;
            }
            leftSide++;
            rightSide--;
        }
    }

    return Palidrime;
}

int main(int argc, const char * argv[]) {
    // insert code here...
    std::string PossiblePalindrome;
    std::cout << "Enter a string to test to see if it is a palindrome.\n";
    std::cin >> PossiblePalindrome;

    std::cout << "The string " << PossiblePalindrome;
    if (IsPalindrome(PossiblePalindrome))
    {
        std::cout << " is";
    }
    else
    {
        std::cout << " is not";
    }
    std::cout << " a palindrome" << std::endl;
}

Answer 1

There are some things to be said about your C version as well, but since you explicitly asked about the C++ version (and also because my C-knowledge is not that great), I will leave those for somebody else to comment on.

General Hints and Tips

1. You are passing possiblePalindrome by value where a pass by const& would be much more appropriate since you don't modify the string.

2. Prefer early return over putting your whole code inside an if-else construct. To my mind, at least,

   if (PossiblePalindrome.size() < 3)
   {
       Palidrime = false;
   }
   else //...
   

   should rather be

   if (PossiblePalindrome.size() < 3)
   {
       return false;
   } //no else
   

   This helps eliminate redundant layers of indentation and makes the code more readable.

3. Since you don't write anything to the argument string, you should use std::string::const_iterator to iterate it (in addition to making the parameter const, see point 1).

4. Please, don't use std::endl. It's horrible. Why? Because it does not do what its name advises and is pretty much redundant. std::endl does write an end-of-line character, but it also flushes the underlying buffer, which is seldom what you want (and if you really need that functionality, you should use std::flush).

Making your Code more C++-y

As you remarked yourself, your current code is not very much C++-like, but we're going to change that by making good use of the standard library. As you know, checking whether a string is a palindrome is equal to checking the to halves of the string for equality, only that the latter half is traversed in reverse order. Luckily for us, checking ranges of elements for equality is one of the things that are needed quite frequently by a lot of people, so C++ offers the very useful std::equal.

std::equal, in its most basic form, takes three iterators: one to the beginning of a range of elements, one to its end, and another one that points to the beginning of the range the elements should be compared with. The only problem here is that we actually need our second range to be iterated in reverse. Again, the STL comes to our rescue. There is std::reverse_iterator, which, who would have guessed, allows iterating in reverse order, and also rbegin, which is a member function of std::string that returns a reverse iterator from the end of the string.

Combining these, we get

bool is_palindrome(std::string const& s) {

    if (s.size() < 3) {
        return false;
    }

    return std::equal(s.begin(), s.end(), s.rbegin());
}

However, as you might have already noticed, we're wasting something here. In particular, we iterate through the whole string although we actually only need to check up to the middle. Thus, we adapt our code accordingly:

bool is_palindrome(std::string const& s) {

    if (s.size() < 3) {
        return false;
    }

    auto end_it = s.begin();
    std::advance(end_it, std::distance(end_it, s.end()) / 2);

    return std::equal(s.begin(), end_it, s.rbegin());
}

(Note that you don't actually need std::advance here, but I prefer to use it as a good practice for the case that I'm writing code where I don't deal with random access iterators.)

This is the best solution I could come up with. If you have any improvements, be free to beat me to it.

Answer 2

• A special case length < 3 seems like a bug. A string aa is a palindrome, and one could successfully argue that a single-letter string is also a palindrome.

• A boolean isPalindrome is redundant, and forces the code to test the effectively same condition twice. An early return is perfectly fine here.

• A traditional idiomatic (and arguably more performant) way to iterate forward is *first++. Similarly, an idiom for iterating backwards is *--last (that also avoids subtracting 1 beforehand):

      last = possiblePalindrome.end();
      while (first < last) {
          if (*first++ != *--last) {
              return false;
          }
      }
      return true;
  

• The naming is very inconsistent. I don't see the reason to spell palindrome in 3 different ways. A capitalization in iSPalendrome is also strange.

Answer 3

I've seen a lot of answers here over-generalizing. You're dealing with a std::string, so you can just do:

bool IsPalindrome(const std::string& s) {
    return std::equal(s.begin(), s.begin() + s.size() / 2, s.rbegin());
}

You don't need anything fancy to find the midpoint. Just add the size/2. As others have mentioned, take the string by const std::string&

Answer 4

Code Review

• Relatively low level

  Usually there is a standard library algorithms for most of uses

• Pass by value

  With std::move() it would be reasonable, but passing by lvalue will incur a redundant copy.

• Undocumented/unclear assumptions

  One of them is that only palindromes of length 3 and higher can be palindromes.

• Verbose control flow

  One could immediately return after seeing that it is not palindrome.

---

I've actually answered one of these before. I wouldn't say it is canonical though. Here is what I've got:

template <typename Container>
constexpr auto middle(const Container& container)
{
    auto half_distance = std::distance(std::begin(container), 
                                       std::end(container)) / 2;
    return std::next(container.begin(), half_distance);
}

bool is_palindrome(const std::string& str) {
    return std::equal(str.cbegin(), middle(str), str.crbegin());
}

Advantages

• Iterators

  This will allow easy transition to some other type

• Standard algorithms

  No reinvention of a wheel, tested and updated by people who (usually) know what they're doing. Very condensed, yet clean code.

---

As people in the comments suggested, one can easily generalize that:

template <typename Container>
constexpr auto middle(const Container& container)
{
    using std::begin;
    using std::end;
    auto half_distance = std::distance(begin(container), 
                                       end(container)) / 2;
    return std::next(begin(container), half_distance);
}

template <typename Container>
bool is_palindrome(const Container& container) {
    using std::cbegin;
    using std::crbegin;
    return std::equal(cbegin(container), middle(container), 
                      crbegin(container));
}

Answer 5

Using the standard functions it becomes relatively simple (a one liner).

#include <iostream>
#include <algorithm>
#include <iterator>

int main()
{
    std::string data = "panap";
    std::cout << std::boolalpha
              << std::equal(std::begin(data),
                            std::begin(data) + (std::size(data) / 2), 
                            std::rbegin(data))
              << "\n";
}

Lets compare this to yours:

Pass by const reference to avoid a copy.

bool IsPalindrome(std::string PossiblePalindrome)

Here you are passing the string by value. This basically causes the string to be copied (an O(n) operation).

Not sure this is true.

    if (PossiblePalindrome.size() < 3)
    {
        Palidrime = false;
    }

Unless they gave you special instructions. A zero and one length string is a palindrome.

Use auto when you can

        std::string::iterator leftSide = PossiblePalindrome.begin();
        std::string::iterator rightSide = PossiblePalindrome.end();

Sure you can go full out and specify the types. But in modern C++ we usually like the compiler to deduce the types (especially if the exact type is not important: for iterators the exact type is not important, just the fact that it is in the group of types that implement an iterator).

        auto leftSide = PossiblePalindrome.begin();
        auto rightSide = PossiblePalindrome.end();

Prefer to use pre-increment.

It makes very little difference in this context (so I am not bashing you for this exact usage). But it does make a tiny difference and if used in the wrong place can cause a difference.

So since the pre-increment achieves the same result and is optimal prefer to use this one as in the long run it will pay off.

        rightSide--;

Why not use a break in the loop?

        while ((leftSide < rightSide) && Palidrime)
        {
            if (*leftSide != *rightSide)
            {
                Palidrime = false;
                // I would just have put a break here.
                // this simplifies the loop test above.
            }
            leftSide++;
            rightSide--;
        }

If you simplify the loop it becomes:

        for (;(leftSide < rightSide); ++leftSide, --rightSide)
        {
            if (*leftSide != *rightSide)
            {
                Palidrime = false;
                break;
            }
        }

Be consistent with braces.

You normally line your braces up on the same horizontal. But here you place it on the end of the line:

int main(int argc, const char * argv[]) {

Both are fine. BUT for neat code you should be consistent in your usage.

Notice that the operator>> only reads a single space separated word.

    std::cin >> PossiblePalindrome;

There are a lot of interesting palindromes that use spaces (that are ignored).

    A man a plan a canal Panama

If you ignore space and capitalization the above is an palindrome. You could have used std::getline() to read a line of text from the user.

Use ternary operator (judicially)

    if (IsPalindrome(PossiblePalindrome))
    {
        std::cout << " is";
    }
    else
    {
        std::cout << " is not";
    }
    std::cout << " a palindrome" << std::endl;

This case can be simplified using the ternary operator?

    std::cout << "The string "
              << PossiblePalindrome
              << " is"
              << (!IsPalindrome(PossiblePalindrome) ? " not":"")
              << " a palindrome" << "\n";

Prefer '\n' over std::endl

The only difference here is a flush of the buffer.
Manually flushing the buffer is actually the major cause of slow down in C++ i/o based code. The system libraries are practically optimal in the timing for flush and any attempt by you will just usually screw things up.

So the general case start with '\n' then test to see if std::endl improves (it generally will not).

Answer 6

Not a complete critique of your code, but

• The condition on the length is wrong. "A" is a palindrome, as is "BB". It's an open question whether "" is a palindrome though.
• No need to copy the string being tested, use a const ref. You're not changing it.

Answer 7

Before coding, did you go over the requirements with the interviewer? Are strings limited to just words? What about sentences/phrases? Any adjustments for capital letters, punctuation, word dividers? Consider that the phrases *A man, a plan, a canal, Panama!", "Was it a car or a cat I saw?", or "No 'x' in Nixon" are considered palindromic phrases.

Also, why do you ignore strings of length 1 and 2? Document the reasoning.

---

int main(int argc, const char * argv[]) {

Omit the parameters of main if you do not intend on utilising command-line arguments.

---

    std::cin >> PossiblePalindrome;

When reading from a stream, check to make sure the read was successful.

---

Simplify your logic.

    std::cout << "The string " << PossiblePalindrome << " is ";
    if (!IsPalindrome(PossiblePalindrome))
    {
        std::cout << "not ";
    }
    std::cout << "a palindrome.\n";

---

Split your library code from your test code.

Instead of letting a user pump in data, grab a testing framework and write actual tests. See Catch2, GoogleTest, or Boost.Test. Here is a Catch2 example:

#include "palindrome.hpp"

#define CATCH_CONFIG_MAIN
#include "catch.hpp"

TEST_CASE( "Empty String", "[empty]" ) {
    REQUIRE( IsPalindrome("") );
}

TEST_CASE( "Short Strings", "[short]" ) {
    REQUIRE( IsPalindrome("ANNA") );
    /* ... */
}

TEST_CASE( "Long Strings", "[long]" ) {
    REQUIRE( IsPalindrome("Degas, are we not drawn onward, no? In union, drawn onward to new eras aged?") );
    /* ... */
}

TEST_CASE( "Absurdly Long Strings", "[absurdly-long]" ) {
    REQUIRE( IsPalindrome("Dennis, Nell, Edna, Leon, Nedra, Anita, Rolf, Nora, Alice, Carol, Leo, Jane, Reed, Dena, Dale, Basil, Rae, Penny, Lana, Dave, Denny, Lena, Ida, Bernadette, Ben, Ray, Lila, Nina, Jo, Ira, Mara, Sara, Mario, Jan, Ina, Lily, Arne, Bette, Dan, Reba, Diane, Lynn, Ed, Eva, Dana, Lynne, Pearl, Isabel, Ada, Ned, Dee, Rena, Joel, Lora, Cecil, Aaron, Flora, Tina, Arden, Noel, and Ellen sinned.") );
    /* ... */
}

See PalindromeList for palindromes to test with. Make sure you also check non-palindromes.

---

bool IsPalindrome(std::string PossiblePalindrome)

For input parameters that aren't modified, only pass cheaply-copied types (2-3 Bytes) by value. Pass anything else by reference to const. There are exceptions (sink or copy required params).

---

bool Palidrime = true;

Be consistent with your spelling.

Rather than tracking the state, simplify the logic and just return as soon as you encounter a bad character.

Prefer the member cbegin()/cend() to make it clear to readers that the elements of the range are immutable.

    if (PossiblePalindrome.size() < 3)
    {
         return false;
    }

    auto leftSide = PossiblePalindrome.cbegin();
    auto rightSide = PossiblePalindrome.cend();

---

    while ((leftSide < rightSide) && Palidrime)
    {
        if (*leftSide != *rightSide)
        {
            Palidrime = false;
        }
        leftSide++;
        rightSide--;
    }

This looks to be a candidate to be a standalone function. As others have pointed out, it's std::equal with a range and its corresponding std::reverse_iterator.

Answer 8

You can remove the flag variables, there is nothing wrong with using a return statement as soon as you know the result.

This is how I would implement it in C, continually compare the start and end characters until they are different or they meet in the middle.

bool isPalindrome(const char* word)
{
    for (const char *b = word, *e = (word + strlen(word) - 1); b < e; ++b, --e)
    {
        if (*b != *e) { return false; }
    }
    return true;
}

In C++ using the same algorithm

bool isPalindrome(const std::string &word)
{
    for (auto b = word.cbegin(), e = word.cend() - 1; b < e; ++b, --e)
    {
        if (*b != *e) { return false; }
    }
    return true;
}

Answer 9

Take care with inputs and outputs

Spot the problem here:

char testString[BUFSIZ];
scanf("%s", testString);

Although testString only has enough space to hold BUFSIZ characters (including the string terminator), we read an unbounded string from standard input. And never test the result of scanf, so we don't know whether any characters were even read.

There's also no checking of the result of printf() - that's arguably not a problem here, but in an interview question, I'd expect to see a comment explaining that you have consciously chosen to skip the check that you would normally put in your production code.

The buffer overrun isn't a problem in the C++ version (as a std::string will expand as necessary), but there is a missing check of cin.good() after reading from it. The idiomatic form is something like

if (std::cin >> PossiblePalindrome) {
    // ...
} else {
    throw std::runtime_error("Failed to read input");
}

Write for localisation

Assembling strings like this can harm the localisability of your messages:

printf("The test string %s is %s a palindrome\n", testString, (iSPalendrome? "" : "Not"));

Not all languages can negate a sentence with a single change to one part like this, so if your program were to be internationalized and ship with message catalogs for each language, this statement would probably need to be re-written. Perhaps something like the following would be better:

printf(iSPalindrome
         ? "The test string %s is a palindrome\n"
         : "The test string %s is not a palindrome\n",
       testString);

But I'd lean towards an if/else so that the compiler can still check that the arguments agree with the format string.

The C++ exhibits a similar problem. Additionally, the C version will output a doubled space ("is a") for the negative case. That could have been avoided by moving one of the spaces into the "Not" - but don't compose strings like that anyway.

Answer 10

For the C++ code I would write the following

template<typename biDiIt, typename compare>
bool
isPalindrome(biDiIt first, biDiIt last, compare comp)
{
  const auto dist = std::distance(first,last);
  const auto rev_last = std::make_reverse_iterator(last);
  const auto mid = std::next(first,dist/2);
  return std::equal(first, mid, rev_last, comp);
}

template<typename biDiIt>
bool
isPalindrome(biDiIt first, biDiIt last)
{
  using value_type = typename std::iterator_traits<biDiIt>::value_type;
  return isPalindrome(first, last, std::equal_to<value_type>() );
}

This is code in the spirit of the standard template library, and it would work for any data structure equipped with bidirectional iterators. It also can use a custom comparision function if you wanted to say, for example that all vowels are equivalent and all constanants are equivalent.

So for your function we would write

bool
isPalindrome(const std::string& input)
{
   return isPalindrome(std::begin(input), std::end(input));
}