Properly checking for palindromes using UTF-8 strings in C++

user_16175252 0
Viewed 125

When trying to answer a question, How to use enqueu, dequeue, push, and peek in a Palindrome?, I suggested a palindrome can be found using std::string by:

bool isPalindrome(const std::string str)
{
    return std::equal(str.begin(), str.end(), str.rbegin(), str.rend());
}

For a Unicode string, I suggested:

bool isPalindrome(const std::u8string str)
{
    std::u8string rstr{str};

    std::reverse(rstr.begin(), rstr.end());

    return str == rstr;
}

I now think this will create problems when you have multibyte characters in the string because the byte-order of the multibyte character is also reversed. Also, some characters will be equivalent to each other in different locales. Therefore, in C++20:

  1. how do you make the comparison robust to multibyte characters?
  2. how do you make the comparison robust to different locales when there can be equivalency between multiple characters?
c++20 c++
1 Answers

Reversing a Unicode string becomes non-trivial. Converting from UTF-8 to UTF-32/UCS-4 is a good start, but not sufficient by itself--Unicode also has combining code points, so two (or more) consecutive code points form a single resulting grapheme (the added code point(s) add(s) diacritic marking to the base character), and for things to work correctly, you need to keep these in the correct order.

So, basically instead of code points, you need to divide the input up into a series of graphemes, and reverse the order of the graphemes, not just the code points.

To deal with multiple different sequences of code points that represent the same sequence of characters, you normally want to do normalization. There are four different normalization forms. In this case, you'd probably want to use NFC or NFD (should be equivalent for this purpose). The NFKC/NFKD forms are primarily for compatibility with other character sets, which it sounds like you probably don't care about.

This can also be non-trivial though. Just for one well known example, consider the German character "ß". This is sort of equivalent to "ss", but only exists in lower-case, since it never occurs at the beginning of a word. So, there's probably room for argument about whether something like Ssaß is a palindrome or not (for the moment ignoring the minor detail that it's not actually a word). For palindromes, most people ignore letter case, so it would be--but your code in the question seems to treat case as significant, in which case it probably shouldn't be.

user_1799100
Related