Pages

Palindrome string

You know what a palindrome is, right? For instance, SOS by ABBA, is a song with a palindromic title played by a pop group with a palindromic name.

It is easy to write a function that detects if a string is a palindrome, so an interviewer sometimes asks it as a first question, just to break the ice.

Here is a no-frills implementation in C:
int cPalindrome(const char* input)
{
    if(input == NULL) // 1
        return 1;

    int len = strlen(input); // 2
    for(int i = 0; i < len / 2; ++i) // 3
    {
        if(input[i] != input[len - i - 1]) // 4
            return 0;
    }

    return 1; // 5
}
1. If the caller pass a NULL, should we consider it a palindrome or not? It is questionable, at it should be a matter of a little chat to decide what the expected behavior should actually be. I voted for the most permissive option.
2. Painfully, we have to loop on the string once, just to get its length. But we have no choice, we can't even start checking the string if we don't know where is its end.
3. We check each couple of elements, moving from the extremes to the center.
4. As soon as we detect a mismatch, we return a "No, sir, this is not a palindrome!".
5. All string checked (notice that it could be even an empty one), no difference spotted, we claim it is a palindrome.

We can rewrite it in C++, and the result is an amazing one-liner:
bool palindrome(const std::string& input)
{
    return std::equal(input.begin(), input.begin() + input.length() / 2, input.rbegin());
}
Right, one line, but an intense one. There are a few things to notice.

No check on NULL string. It is not possible to convert a NULL to a string object, so such test, when required, should be moved outside the function.

To compare the elements in the string, I used the STL equal() function (defined in the algorithm include file). First two parameters are the delimiter for the first sequence to be checked, third one is the begin of the second sequence. Notice that the third parameter is rbegin(), the "reverse begin" of the string, the iterator to the last valid element of the container (or, in this case, string) that, incremented, moves to the left, and not to the right, as we usually expect in an iterator.

A variation to this classical question, is asking to write it as a recursive function. Here is a possible C++ implementation:
bool rPalindrome(const std::string& input)
{
    if(input.length() < 2) // 1
        return true;
    if(input.front() == input.back()) // 2
        return rPalindrome(input.substr(1, input.length() - 2)); // 3
    return false; // 4
}
1. Empty strings, or single-character ones, are palindrome, without need of any other test.
2. The current string has more that two characters, let's check the one to the extreme left with the one to the extreme right. If they are the same, the string is a palindrome if and only if the internal string is (recursively) a palindrome.
3. So we check the internal string, that is extracted from the current one using the STL string::substr() method.
4. Otherwise the current string is not a palindrome.

No comments:

Post a Comment