# Checking for a palindrome

What I'm basically wondering is if there's anything that is possible to improve in this C++ code:

#include <cstddef>
#include <string>

bool is_palindromic(std::string s)
{
std::size_t i = 0;
std::size_t j = s.length() - 1;
while (i < j) {
if (s[i++] != s[j--]) {
return false;
}
}
return true;
}

• Yep. Try a for loop. Learn how to use references. Consider accidental mutation. – Martin York Nov 20 '13 at 17:08
• Stepping outside the C++ code a bit, make sure you have a clear definition of what qualifies as a palindrome. Are there things (such as spaces or punctuation or letter case) that should be ignored: "Sir, I’m Iris." or just "SIRIMIRIS"? – Michael Urman Nov 20 '13 at 22:13
• "A man a plan a canal Panama" also considered a palindrome. – Martin York Nov 22 '13 at 17:20
• "A man a plan a canal Panama" that's not a palindrome... – Max Nov 28 '13 at 12:04
• – Mathieu Guindon Nov 29 '13 at 1:52

I wanted to offer a different angle of better. This code could be more generic. Why is it tied to exactly std::string - what if I need to check palindromic nature of std::wstring or the contents of a std::vector<T>? How about std::list<T> or std::map<T> (if palindromic can even mean anything on a std::map)? Here's how you can handle all of those with a single function:

template <typename Sequence>
bool is_palindromic(const Sequence& seq)
{
auto count = seq.size() / 2; // rounded down is fine, as a middle element matches itself
auto i = seq.begin();        // prefer std::begin(seq) in C++14
auto j = seq.rbegin();       // prefer std::rbegin(seq) in C++14

for (Sequence::size_type c = 0; c < count; ++c, ++i, ++j)
{
if (*i != *j)
return false;
}
return true; // considers sequences without mismatched characters to be palindromes
}


Note that I incorporated the other comments I agree with - in particular passing by const reference, and using the sequence's size_type. I'm not sure how to best support arrays, however; while std::[r]begin will handle arrays, I don't believe arrays have a .size() or ::size_type to use. I guess that means they need their own overload, or at least some overloaded helpers.

• Use std::distance(std::begin(seq), std::end(seq)) if you want to have a generic way to handle the size. With it, you can handle arrays. I don't know whether it is specialized for random-access iterators; if not, your code may be slower. – Morwenn Nov 20 '13 at 18:58
• Ah, std::distance sounds great for random access and thus supporting arrays. However it's linear on non-random access, so would be slower on std::list (though no worse algorithmically). Thanks for the idea at least! – Michael Urman Nov 20 '13 at 19:14

First of all, you should pass the std::string by const reference and not by value, therefore, replace std::string s by const std::string& s, otherwise you will make a whole copy of the string everytime you invoke the function.

Also, you program may crash if the std::string is empty since you're doing std::size_t j = s.length() - 1;. If s.length() == 0, j will probably be a big number and you will end up with a segfault due to an out of range index.

As suggested by Loki in the comments, you could also use a for loop instead of a while loop in order for your code to look cleaner.

Yet another suggestion by Jamal: using std::string::size_type instead of std::size_t (and removing #include <cstddef> by the way) would be more idiomatic. The type returned by std::string::length is not required to be std::size_t but std::string::size_type.

Therefore, I would rewrite it as:

bool is_palindromic(const std::string& s)
{
if (s.empty())
{
// You can return true if you think that
// an empty string is a palyndrome
return false;
}
for (std::string::size_type i=0, j=s.length()-1
; i < j ; ++i, --j)
{
if (s[i] != s[j]) {
return false;
}
}
return true;
}

• +1 looks good. Just one nitpick: use std::string::size_type instead of std::size_t. – Jamal Nov 20 '13 at 17:31
• Looks like you want --j instead of ++j. – Michael Urman Nov 20 '13 at 18:22
• +1 for it's proximity to the original version and for catching the empty case ! – Wolf Nov 26 '13 at 14:40
• ...BTW: isn't an empty string a palindrome? – Wolf Nov 26 '13 at 14:41
• I'd agree, if there was something special referred in the question, maybe a definition like this. In lack of such, I prefer the idea of empty strings as palindromes. – Wolf Nov 26 '13 at 18:47

I just wanted to chime in with the "lazy" (if not performant) way of doing this, using reverse iterators:

bool is_palindrome(const std::string& s)
{
return s == std::string(s.rbegin(), s.rend());
}


This is very simple and very readable. You could expand this to do things like remove punctuation if you want, but it gets a bit trickier (although it's still short):

// Note that the pass by value is intentional here, so we don't modify
// the original string when using std::remove_if
bool is_palindrome(std::string s)
{
auto it = std::remove_if(s.begin(), s.end(), [](char c) { return !std::isalpha(c); });
return std::equal(s.begin(), it, std::reverse_iterator<std::string::iterator>(it));
}


This can likewise be made into a template that will work with any sequence with very little effort.

Searching for something as symmetrical as palindromes themselves, I came to this somewhat picturesque solution, that doesn't handle the empty string in a specific way, but as palindromic:

#include <string>

bool is_palindromic(const std::string& s)
{
std::string::const_iterator start = s.begin();
std::string::const_iterator end = s.end();
while (start < end) {
if (*(start++) != *(--end)) {
return false;
}
}
return true;
}


Its major drawback is the redundant check for self-equality of the central char.