By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
446,412 Members | 917 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 446,412 IT Pros & Developers. It's quick & easy.

Better implementation of "isPalindromic"

P: n/a
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;
}

Jun 30 '06 #1
Share this Question
Share on Google+
10 Replies


P: n/a
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;
}

Jun 30 '06 #2

P: n/a
return equal(str.begin(), str.end(), str.rbegin());

Jun 30 '06 #3

P: n/a
<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
Jun 30 '06 #4

P: n/a
Chandu wrote:
return equal(str.begin(), str.end(), str.rbegin());


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

Cheers! --M

Jun 30 '06 #5

P: n/a
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


Jun 30 '06 #6

P: n/a
Grr, I meant
int l = s.length()-1;

sba.nospam.ke...@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


Jun 30 '06 #7

P: n/a

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.

Jun 30 '06 #8

P: n/a
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


Jun 30 '06 #9

P: n/a
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;
}


Jun 30 '06 #10

P: n/a
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

Jun 30 '06 #11

This discussion thread is closed

Replies have been disabled for this discussion.