11
\$\begingroup\$

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;
}
\$\endgroup\$
  • 8
    \$\begingroup\$ Since you’ve posted the C code: register might be valid C but that’s pretty irrelevant on a Code Review site. Is it good C? No: it’s pretty much obsolete. In fact, if the compiler honours it at all it’s more likely than not to screw with the compiler’s own, much superior optimisation logic. Don’t use register. Definitely not here. \$\endgroup\$ – Konrad Rudolph Nov 21 '17 at 22:36
  • \$\begingroup\$ @KonradRudolph It does tell the compiler that you're never going to dereference the variable... not that it doesn't know that in 80% of cases. \$\endgroup\$ – wizzwizz4 Nov 22 '17 at 18:14
  • \$\begingroup\$ @wizzwizz4 My point exactly. The compile can figure this out on its own just fine. \$\endgroup\$ – Konrad Rudolph Nov 22 '17 at 18:15
  • \$\begingroup\$ @pacmaninbw In the C++ code you have a variable called Palidrime. Is that a typo or am I just unaware of the word? \$\endgroup\$ – Maybe_Factor Nov 23 '17 at 5:54
  • \$\begingroup\$ @Maybe_Factor: And in the C code, a variable named Palendrome. I think typos... \$\endgroup\$ – Matthieu M. Nov 23 '17 at 8:14

10 Answers 10

14
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ I'd use std::next instead of std::advance to avoid creating variable and then changing it's value \$\endgroup\$ – RiaD Nov 21 '17 at 20:12
  • \$\begingroup\$ @RiaD Inlining the variable here would be a little too much for one line, I think. I'd say either std::next or std::advance is fine. \$\endgroup\$ – Ben Steffan Nov 21 '17 at 20:40
  • 2
    \$\begingroup\$ I don't mean inline it but I think it's fine too), but auto end_it = std::next(end_it, std::distance(end_it, s.end()) / 2); it's easier to reason about things that don't change. \$\endgroup\$ – RiaD Nov 21 '17 at 21:16
  • \$\begingroup\$ But I'd agree that it's not super important \$\endgroup\$ – RiaD Nov 21 '17 at 21:16
  • 4
    \$\begingroup\$ I assume you meant auto end_it = std::next(s.begin(), std::distance(s.begin(), s.end()) / 2);, @RiaD? And while we're at it, I'd prefer to rename it to, say, middle_it. But I do agree that the line auto end_it = s.begin(); just looks wrong, and forces one to look twice to figure out that it's not a bug in the context where it's used. Better IMO to just immediately set the iterator to the value it's actually going to have. \$\endgroup\$ – Ilmari Karonen Nov 22 '17 at 4:56
21
\$\begingroup\$
  • 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.

\$\endgroup\$
  • \$\begingroup\$ Shouldn't backwards be *last--? \$\endgroup\$ – Incomputable Nov 21 '17 at 18:52
  • \$\begingroup\$ @incomputable No. Just don't decrement it beforehand. See edit. \$\endgroup\$ – vnp Nov 21 '17 at 18:54
  • 2
    \$\begingroup\$ arguably more performant => really? I see no reason to obfuscate the code with piling as many operations as possible on a single line. \$\endgroup\$ – Matthieu M. Nov 23 '17 at 8:16
13
\$\begingroup\$

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&

\$\endgroup\$
  • \$\begingroup\$ So @BenSteffan's answer? The over-generalizing critique of other answers probably could have just been a comment. \$\endgroup\$ – Snowhawk Nov 21 '17 at 23:01
  • 2
    \$\begingroup\$ @Snowhawk At least 3 answers here got that midpoint using std::next, std::distance, function templates, or all of the above. Could've just added. Nothing wrong with those approaches for generic code, but prefer the simplest method. \$\endgroup\$ – David Nov 21 '17 at 23:06
  • 2
    \$\begingroup\$ @LokiAstari there's some contention over that advice. Personally, I'm with the camp that says use the free functions when you need to use them generically (such as when the container is a template type), otherwise use the member functions. I don't believe in over-generalizing in C++ as it can often be more complicated more verbose code. \$\endgroup\$ – David Nov 22 '17 at 21:13
  • 1
    \$\begingroup\$ @LokiAstari, I believe Herb Sutter is on the other camp. There was a proposal authored by him, but I believe it was not accepted. \$\endgroup\$ – Incomputable Nov 23 '17 at 5:18
  • 3
    \$\begingroup\$ @LokiAstari: Actually, if you go the free function route, it should really be using std::begin; begin(c), so that if a type defines a free-standing begin rather than a member function begin it's also picked up. And that really verbose, compared to c.begin(). I don't see the point of using free-standing begin/end when unnecessary. \$\endgroup\$ – Matthieu M. Nov 23 '17 at 8:20
6
\$\begingroup\$

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));
}
\$\endgroup\$
  • \$\begingroup\$ OP's code and your code are not functionally equivalent. In particular, OP's code is case sensitive whereas yours is not. \$\endgroup\$ – Ben Steffan Nov 21 '17 at 18:48
  • \$\begingroup\$ @BenSteffan, thanks for noticing. I kind of skipped the problem definition, a really bad habit. \$\endgroup\$ – Incomputable Nov 21 '17 at 18:50
  • \$\begingroup\$ Prefer using std::begin(str) and similar functions over calling str.cbegin() directly (after all, you already do it in middle). Also, that way, is_palindrome could easily be generalized to check any container whether it is equal to its reversal. template<typename Container> bool is_palindrome(const Container& cont) { return std::equal(std::begin(cont), middle(cont), std::rbegin(cont)); } \$\endgroup\$ – hoffmale Nov 21 '17 at 19:01
  • \$\begingroup\$ @Snowhawk, thanks. This might as well be canonical now. \$\endgroup\$ – Incomputable Nov 21 '17 at 19:20
  • 1
    \$\begingroup\$ This is a great solution (+1) but it’s not a code review. \$\endgroup\$ – Konrad Rudolph Nov 21 '17 at 22:29
5
\$\begingroup\$

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 modern C++ we usally 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 littel 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 read 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 capatolization 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++ io 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).

\$\endgroup\$
  • \$\begingroup\$ Palidrime? In the future it might be worth copy/pasting from the question directly... \$\endgroup\$ – Nic Hartley Nov 22 '17 at 16:13
  • \$\begingroup\$ @Toby I'm not sure how that matters? It's spelled isPalindrome in the question, not Palidrime. (And if the question has been edited, which I can't easily tell on mobile, then it should be rolled back and the asker informed that code in questions shouldn't be changed after you get an answer) \$\endgroup\$ – Nic Hartley Nov 22 '17 at 16:30
4
\$\begingroup\$

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.
\$\endgroup\$
4
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ A lot of good points. I don't remember the exact requirement, I only thought of single words when I was asked the question. I should have asked that specific question. \$\endgroup\$ – pacmaninbw Nov 22 '17 at 16:53
2
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Yes the C version added the space, I changed it in the C++ version. It's funny, after all the times I beat on people to check input for errors, I forgot it myself. I chose BUFSIZ because it's a common header macro, and it generally evaluates to 1024. \$\endgroup\$ – pacmaninbw Nov 22 '17 at 16:47
1
\$\begingroup\$

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));
}
\$\endgroup\$
1
\$\begingroup\$

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;
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.