Checking if a String is a Palindrome

A palindrome is a word, phrase, number, or other sequence of characters that reads the same forward and backward. Checking if a string is a palindrome is a common programming task. Here's an efficient way to do this in C++ using std::string:

1#include <iostream>
2#include <string>
3#include <algorithm>
4#include <cctype>
5#include <vector>
6
7bool is_palindrome(const std::string& str) {
8  if (str.empty()) {
9    return true;
10  }
11
12  auto left = str.begin();
13  auto right = str.end() - 1;
14
15  while (left < right) {
16    // Skip non-alphanumeric characters
17    while (left < right && !std::isalnum(*left))
18      ++left;
19    while (left < right && !std::isalnum(*right))
20      --right;
21
22    if (std::tolower(*left) != std::tolower(*right)) {
23      return false;
24    }
25
26    ++left;
27    --right;
28  }
29
30  return true;
31}
32
33int main() {
34  std::vector<std::string> tests{
35    "A man, a plan, a canal: Panama", "race a car",
36    "Was it a car or a cat I saw?", "Hello, World!",
37    ""  // empty string
38  };
39
40  for (const auto& test : tests) {
41    std::cout << "\"" << test << "\" is " << (
42      is_palindrome(test) ?
43      "a palindrome" : "not a palindrome"
44    ) << '\n';
45  }
46}

1"A man, a plan, a canal: Panama" is a palindrome
2"race a car" is not a palindrome
3"Was it a car or a cat I saw?" is a palindrome
4"Hello, World!" is not a palindrome
5"" is a palindrome

Let's break down the is_palindrome() function:

1. We use two iterators, left and right, starting from the beginning and end of the string respectively.
2. We skip non-alphanumeric characters using std::isalnum().
3. We compare characters case-insensitively using std::tolower().
4. If we find a mismatch, we return false.
5. If we make it through the entire string without finding a mismatch, we return true.

This approach is efficient because:

• It works in-place, without creating any new strings.
• It stops as soon as it finds a mismatch.
• It only traverses half the string in the worst case.

For a simpler implementation that considers all characters and is case-sensitive, you could use std::equal():

1bool simple_palindrome(const std::string& str) {
2  return std::equal(
3    str.begin(),
4    str.begin() + str.length() / 2,
5    str.rbegin()
6  );
7}

This method is shorter but less flexible, as it doesn't ignore non-alphanumeric characters or handle case-insensitivity.

For very long strings, you might consider using std::string_view (C++17) to avoid copying:

1#include <string_view>
2
3bool is_palindrome(std::string_view sv) {
4  // Similar implementation as before,
5  // but using string_view
6}

Remember, the most appropriate method depends on your specific requirements, such as whether you need to ignore punctuation and whitespace, whether the check should be case-sensitive, and what constitutes a valid character in your palindrome definition.