Better implementation of "isPalindromic"

[leonadavinci]

I've tried to make a function that takes a string and tells whether
this is Palindromic or not. The code I've written is below. I try to
find ways to optimize the performance of my code. Any suggestions?
#include <string>
#include <iostream>
#include <algorithm>
#include <ctype.h>
using std::string;
using std::cout;
using std::reverse;
void toLower (const string& str,string& dest)
{
string::const_iterator i;
for(i=str.begin();i!=str.end();++i)
dest+=tolower(*i);
}
void removePunctuation (const string& str,string& dest)
{
string::const_iterator i;
for(i=str.begin();i!=str.end();++i)
if(isalpha(*i)) dest+=*i;
}
bool isPalindrome (string& str)
{
string reversed=str;
reverse(reversed.begin(),reversed.end());
return str==reversed;
}

bool isPalindromic (const string& phrase)
{
string dest0,dest1;
toLower(phrase,dest0);
removePunctuation(dest0,dest1);
return isPalindrome(dest1);
}
int main(int argc, char* argv[])
{
cout<<isPalindromic("anna");
return 0;
}

[red floyd]

le**********@gmail.com wrote:

I've tried to make a function that takes a string and tells whether
this is Palindromic or not. The code I've written is below. I try to
find ways to optimize the performance of my code. Any suggestions?
#include <string>
#include <iostream>
#include <algorithm>
#include <ctype.h>
using std::string;
using std::cout;
using std::reverse;
void toLower (const string& str,string& dest)
{
string::const_iterator i;
for(i=str.begin();i!=str.end();++i)
dest+=tolower(*i);
}
void removePunctuation (const string& str,string& dest)
{
string::const_iterator i;
for(i=str.begin();i!=str.end();++i)
if(isalpha(*i)) dest+=*i;
}
bool isPalindrome (string& str)
{ return str = string(str.rbegin(),str.rend()); string reversed=str;
reverse(reversed.begin(),reversed.end());
return str==reversed;
}

bool isPalindromic (const string& phrase)
{
string dest0,dest1;
toLower(phrase,dest0);
removePunctuation(dest0,dest1);
return isPalindrome(dest1);
}
int main(int argc, char* argv[])
{
cout<<isPalindromic("anna");
return 0;
}

[Chandu]

return equal(str.begin(), str.end(), str.rbegin());

[Stuart Golodetz]

<le**********@gmail.com> wrote in message
news:11*********************@y41g2000cwy.googlegro ups.com...

I've tried to make a function that takes a string and tells whether
this is Palindromic or not. The code I've written is below. I try to
find ways to optimize the performance of my code. Any suggestions?
#include <string>
#include <iostream>
#include <algorithm>
#include <ctype.h>
using std::string;
using std::cout;
using std::reverse;
void toLower (const string& str,string& dest)
{
string::const_iterator i;
for(i=str.begin();i!=str.end();++i)
dest+=tolower(*i);
}
void removePunctuation (const string& str,string& dest)
{
string::const_iterator i;
for(i=str.begin();i!=str.end();++i)
if(isalpha(*i)) dest+=*i;
}
bool isPalindrome (string& str)
{
string reversed=str;
reverse(reversed.begin(),reversed.end());
return str==reversed;
}

bool isPalindromic (const string& phrase)
{
string dest0,dest1;
toLower(phrase,dest0);
removePunctuation(dest0,dest1);
return isPalindrome(dest1);
}
int main(int argc, char* argv[])
{
cout<<isPalindromic("anna");
return 0;
}

The current implementation of isPalindrome is doing too much work, as you
seem to have gathered. You don't need to make a reversed copy of the string,
or do (at most) str.length() comparisons. You can get away with (at most)
str.length() / 2 comparisons and no additional space:

bool isPalindrome(const std::string& s)
{
for(int i=0, len=s.length(); i<len/2; ++i)
{
if(s[i] != s[len-1-i]) return false;
}
return true;
}

Hope this helps :)
Stu

[mlimber]

Chandu wrote:

return equal(str.begin(), str.end(), str.rbegin());

return equal(str.begin(), str.begin() + str.length()/2, str.rbegin());

Cheers! --M

[sba.nospam.ker48]

I would do something like this, to take into account spaces,
punctuation, and capitalization.

bool isPalindrome(const std::string& s)
{
int l = s.length();
int b=0;
int e=l;

do
{
while ( b < l && !isalpha(s[b]) ) b++;
while ( e >= 0 && !isalpha(s[e]) ) e--;
if ( b <= e && tolower(s[b]) != tolower(s[e]) ) return false;
b++; e--;
}
while ( b <= e );

return true;
}

Stuart Golodetz wrote:

<le**********@gmail.com> wrote in message
news:11*********************@y41g2000cwy.googlegro ups.com...

I've tried to make a function that takes a string and tells whether
this is Palindromic or not. The code I've written is below. I try to
find ways to optimize the performance of my code. Any suggestions?
#include <string>
#include <iostream>
#include <algorithm>
#include <ctype.h>
using std::string;
using std::cout;
using std::reverse;
void toLower (const string& str,string& dest)
{
string::const_iterator i;
for(i=str.begin();i!=str.end();++i)
dest+=tolower(*i);
}
void removePunctuation (const string& str,string& dest)
{
string::const_iterator i;
for(i=str.begin();i!=str.end();++i)
if(isalpha(*i)) dest+=*i;
}
bool isPalindrome (string& str)
{
string reversed=str;
reverse(reversed.begin(),reversed.end());
return str==reversed;
}

bool isPalindromic (const string& phrase)
{
string dest0,dest1;
toLower(phrase,dest0);
removePunctuation(dest0,dest1);
return isPalindrome(dest1);
}
int main(int argc, char* argv[])
{
cout<<isPalindromic("anna");
return 0;
}

The current implementation of isPalindrome is doing too much work, as you
seem to have gathered. You don't need to make a reversed copy of the string,
or do (at most) str.length() comparisons. You can get away with (at most)
str.length() / 2 comparisons and no additional space:

bool isPalindrome(const std::string& s)
{
for(int i=0, len=s.length(); i<len/2; ++i)
{
if(s[i] != s[len-1-i]) return false;
}
return true;
}

Hope this helps :)
Stu

[sba.nospam.ker48]

Grr, I meant
int l = s.length()-1;

[e-mail] wrote:

I would do something like this, to take into account spaces,
punctuation, and capitalization.

bool isPalindrome(const std::string& s)
{
int l = s.length();
int b=0;
int e=l;

do
{
while ( b < l && !isalpha(s[b]) ) b++;
while ( e >= 0 && !isalpha(s[e]) ) e--;
if ( b <= e && tolower(s[b]) != tolower(s[e]) ) return false;
b++; e--;
}
while ( b <= e );

return true;
}

Stuart Golodetz wrote:

<le**********@gmail.com> wrote in message
news:11*********************@y41g2000cwy.googlegro ups.com...

I've tried to make a function that takes a string and tells whether
this is Palindromic or not. The code I've written is below. I try to
find ways to optimize the performance of my code. Any suggestions?
#include <string>
#include <iostream>
#include <algorithm>
#include <ctype.h>
using std::string;
using std::cout;
using std::reverse;
void toLower (const string& str,string& dest)
{
string::const_iterator i;
for(i=str.begin();i!=str.end();++i)
dest+=tolower(*i);
}
void removePunctuation (const string& str,string& dest)
{
string::const_iterator i;
for(i=str.begin();i!=str.end();++i)
if(isalpha(*i)) dest+=*i;
}
bool isPalindrome (string& str)
{
string reversed=str;
reverse(reversed.begin(),reversed.end());
return str==reversed;
}

bool isPalindromic (const string& phrase)
{
string dest0,dest1;
toLower(phrase,dest0);
removePunctuation(dest0,dest1);
return isPalindrome(dest1);
}
int main(int argc, char* argv[])
{
cout<<isPalindromic("anna");
return 0;
}

The current implementation of isPalindrome is doing too much work, as you
seem to have gathered. You don't need to make a reversed copy of the string,
or do (at most) str.length() comparisons. You can get away with (at most)
str.length() / 2 comparisons and no additional space:

bool isPalindrome(const std::string& s)
{
for(int i=0, len=s.length(); i<len/2; ++i)
{
if(s[i] != s[len-1-i]) return false;
}
return true;
}

Hope this helps :)
Stu

[leonadavinci]

sb**************@gmail.com wrote:

I would do something like this, to take into account spaces,
punctuation, and capitalization.

bool isPalindrome(const std::string& s)
{
int l = s.length();
int b=0;
int e=l;

do
{
while ( b < l && !isalpha(s[b]) ) b++;
while ( e >= 0 && !isalpha(s[e]) ) e--;
if ( b <= e && tolower(s[b]) != tolower(s[e]) ) return false;
b++; e--;
}
while ( b <= e );

return true;
}

Stuart Golodetz wrote:

<le**********@gmail.com> wrote in message
news:11*********************@y41g2000cwy.googlegro ups.com...

I've tried to make a function that takes a string and tells whether
this is Palindromic or not. The code I've written is below. I try to
find ways to optimize the performance of my code. Any suggestions?
#include <string>
#include <iostream>
#include <algorithm>
#include <ctype.h>
using std::string;
using std::cout;
using std::reverse;
void toLower (const string& str,string& dest)
{
string::const_iterator i;
for(i=str.begin();i!=str.end();++i)
dest+=tolower(*i);
}
void removePunctuation (const string& str,string& dest)
{
string::const_iterator i;
for(i=str.begin();i!=str.end();++i)
if(isalpha(*i)) dest+=*i;
}
bool isPalindrome (string& str)
{
string reversed=str;
reverse(reversed.begin(),reversed.end());
return str==reversed;
}

bool isPalindromic (const string& phrase)
{
string dest0,dest1;
toLower(phrase,dest0);
removePunctuation(dest0,dest1);
return isPalindrome(dest1);
}
int main(int argc, char* argv[])
{
cout<<isPalindromic("anna");
return 0;
}

The current implementation of isPalindrome is doing too much work, as you
seem to have gathered. You don't need to make a reversed copy of the string,
or do (at most) str.length() comparisons. You can get away with (at most)
str.length() / 2 comparisons and no additional space:

bool isPalindrome(const std::string& s)
{
for(int i=0, len=s.length(); i<len/2; ++i)
{
if(s[i] != s[len-1-i]) return false;
}
return true;
}

Hope this helps :)
Stu

Very good implementation.

[leonadavinci]

Very good implementation
sb**************@gmail.com wrote:

I would do something like this, to take into account spaces,
punctuation, and capitalization.

bool isPalindrome(const std::string& s)
{
int l = s.length();
int b=0;
int e=l;

do
{
while ( b < l && !isalpha(s[b]) ) b++;
while ( e >= 0 && !isalpha(s[e]) ) e--;
if ( b <= e && tolower(s[b]) != tolower(s[e]) ) return false;
b++; e--;
}
while ( b <= e );

return true;
}

Stuart Golodetz wrote:

<le**********@gmail.com> wrote in message
news:11*********************@y41g2000cwy.googlegro ups.com...

I've tried to make a function that takes a string and tells whether
this is Palindromic or not. The code I've written is below. I try to
find ways to optimize the performance of my code. Any suggestions?
#include <string>
#include <iostream>
#include <algorithm>
#include <ctype.h>
using std::string;
using std::cout;
using std::reverse;
void toLower (const string& str,string& dest)
{
string::const_iterator i;
for(i=str.begin();i!=str.end();++i)
dest+=tolower(*i);
}
void removePunctuation (const string& str,string& dest)
{
string::const_iterator i;
for(i=str.begin();i!=str.end();++i)
if(isalpha(*i)) dest+=*i;
}
bool isPalindrome (string& str)
{
string reversed=str;
reverse(reversed.begin(),reversed.end());
return str==reversed;
}

bool isPalindromic (const string& phrase)
{
string dest0,dest1;
toLower(phrase,dest0);
removePunctuation(dest0,dest1);
return isPalindrome(dest1);
}
int main(int argc, char* argv[])
{
cout<<isPalindromic("anna");
return 0;
}

The current implementation of isPalindrome is doing too much work, as you
seem to have gathered. You don't need to make a reversed copy of the string,
or do (at most) str.length() comparisons. You can get away with (at most)
str.length() / 2 comparisons and no additional space:

bool isPalindrome(const std::string& s)
{
for(int i=0, len=s.length(); i<len/2; ++i)
{
if(s[i] != s[len-1-i]) return false;
}
return true;
}

Hope this helps :)
Stu

[Markus Schoder]

le**********@gmail.com wrote:

I've tried to make a function that takes a string and tells whether
this is Palindromic or not. The code I've written is below. I try to
find ways to optimize the performance of my code. Any suggestions?
#include <string>
#include <iostream>
#include <algorithm>
#include <ctype.h>
using std::string;
using std::cout;
using std::reverse;
void toLower (const string& str,string& dest)
{
string::const_iterator i;
for(i=str.begin();i!=str.end();++i)
dest+=tolower(*i);
}
void removePunctuation (const string& str,string& dest)
{
string::const_iterator i;
for(i=str.begin();i!=str.end();++i)
if(isalpha(*i)) dest+=*i;
}
bool isPalindrome (string& str)
{
string reversed=str;
reverse(reversed.begin(),reversed.end());
return str==reversed;
}
bool isPalindrome(const string &s)
{
const size_t n = s.size();
for(size_t i = 0; i < n / 2; ++i)
if(s[i] != s[n - i - 1])
return false;
return true;
}

Should give a huge performance improvement for small strings (no memory
allocation required) and strings that are no palindromes.
bool isPalindromic (const string& phrase)
{
string dest0,dest1;
toLower(phrase,dest0);
removePunctuation(dest0,dest1);
return isPalindrome(dest1);
}
int main(int argc, char* argv[])
{
cout<<isPalindromic("anna");
return 0;
}

[Luke Meyers]

mlimber wrote:

Chandu wrote:

return equal(str.begin(), str.end(), str.rbegin());

return equal(str.begin(), str.begin() + str.length()/2, str.rbegin());

I really like these implementations, as examples of the utility of STL
algorithms. However, they do not solve the same problem as the
original code. The original code appears to remove punctuation and
spacing, and be case-insensitive.

One way to fix things so that the above code would still work would be
to write an iterator adapter that converts to lower case and discards
non-alphabetic characters.

Luke