Better implementation of "isPalindromic"

L

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;
}
 
R

red floyd

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)
{
Click to expand...
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;
}
Click to expand...
 
S

Stuart Golodetz

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;
}
Click to expand...

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 != s[len-1-i]) return false;
}
return true;
}

Hope this helps :)
Stu
 
G

Guest

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++;
while ( e >= 0 && !isalpha(s[e]) ) e--;
if ( b <= e && tolower(s) != tolower(s[e]) ) return false;
b++; e--;
}
while ( b <= e );

return true;
}



Stuart said:
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;
}
Click to expand...

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 != s[len-1-i]) return false;
}
return true;
}

Hope this helps :)
Stu
Click to expand...
 
G

Guest

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

[email protected] said:
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++;
while ( e >= 0 && !isalpha(s[e]) ) e--;
if ( b <= e && tolower(s) != tolower(s[e]) ) return false;
b++; e--;
}
while ( b <= e );

return true;
}



Stuart said:
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;
}
Click to expand...

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 != s[len-1-i]) return false;
}
return true;
}

Hope this helps :)
Stu
Click to expand...
Click to expand...
 
L

leonadavinci

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++;
while ( e >= 0 && !isalpha(s[e]) ) e--;
if ( b <= e && tolower(s) != tolower(s[e]) ) return false;
b++; e--;
}
while ( b <= e );

return true;
}



Stuart said:
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;
}
Click to expand...

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 != s[len-1-i]) return false;
}
return true;
}

Hope this helps :)
Stu
Click to expand...
Click to expand...



Very good implementation.
 
L

leonadavinci

Very good implementation
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++;
while ( e >= 0 && !isalpha(s[e]) ) e--;
if ( b <= e && tolower(s) != tolower(s[e]) ) return false;
b++; e--;
}
while ( b <= e );

return true;
}



Stuart said:
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;
}
Click to expand...

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 != s[len-1-i]) return false;
}
return true;
}

Hope this helps :)
Stu
Click to expand...
Click to expand...
 
M

Markus Schoder

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;
}
Click to expand...

bool isPalindrome(const string &s)
{
const size_t n = s.size();
for(size_t i = 0; i < n / 2; ++i)
if(s != 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;
}
Click to expand...
 
L

Luke Meyers

mlimber said:
return equal(str.begin(), str.begin() + str.length()/2, str.rbegin());
Click to expand...

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
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Similar Threads

RSA implementation issues in public key pem loader function 0
Lexical Analysis on C++ 1
Rich Text Format (RTF) Document Builder in C++: Code and Features 0
Chatbot 0
Database Manager: A C++ Console Application 14
Console Interactive File Manager for Protected Files on Windows 0
TF-IDF 2
Mini Web Server in C++ (Part One) 4

Members online

No members online now.
Total: 267 (members: 0, guests: 267)
Robots: 288

Forum statistics

Threads
474,432
Messages
2,571,682
Members
48,796
Latest member
Greg L.

Latest Threads

Top