0

I want to write a method to determine if a given string is a palindrome. E.g. "Madam I'm Adam", or "A man, a plan, a canal, Panama".

The prototype for the function is:

bool is_palindrome(char const * str)

I have a simple logic to check for equality by moving forward & backward from extreme ends of the string. But, i would like to know how many efficient ways to do this ? All ideas welcome from C++ gurus..

duffymo
  • 305,152
  • 44
  • 369
  • 561
Nepz Solutions
  • 111
  • 1
  • 5
  • There are http://stackoverflow.com/questions/248161/palindrome-detection-efficiency and http://stackoverflow.com/questions/228518/palindrome-golf. Possible dup? – pmr Jul 03 '10 at 11:17
  • Note that both your examples are only palindromes if you rigorously ignore white space, punctuation, and capitalization (a nearly universal condition, BTW). How will this effect your approach? Is it worth code for variants that enforce one or more of those? How would you do that? Can you provide a clean interface to all possible combinations? Once you've done that, *then* you understand your problem. Cheers. – dmckee --- ex-moderator kitten Jul 03 '10 at 22:58

1 Answers1

1

I don't think there is a much more efficient way, you do have to compare every character in the string.

Possible optimisations: You only have to check the first half of the string, and you can break out early as soon as you find a mismatch.

bool is_palindrome(char const * str) 
{
    size_t len = strlen(str);
    bool isPalindrome = false;    // It's debatable if a blank string is a palindrome or not

    for(int i = 0; i < len / 2; i++)
    {
        if(str[i] != str[len - i - 1])
        {
            isPalindrome = false;
            break;
        }
        isPalindrome = true;
    }

    return isPalindrome;
}
DanDan
  • 10,462
  • 8
  • 53
  • 69
  • Compiled code might be tighter if the source code used two pointers instead of an array indexer; e.g. `if (*startPtr++ != *endPtr--) {...}` – ChrisW Jul 03 '10 at 11:55