Thread: Palindrome checking

  1. #1
    Registered User
    Join Date
    Aug 2009
    Posts
    3

    Palindrome checking

    Hi all! I'm trying to write some code to check whether a string is a palindrome or not. It must ignore all the non-alphabet chars. For example, "Madam, I'm Adam." is considered a palindrome. I have two pieces of code below. Please tell me which one is better, and if there are better ones. Thank you!

    Code:
    #include <iostream>
    #include <string>
    #include <cctype>
    
    bool isPalindrome(const std::string& s);
    
    int main()
    {
    	using std::cout;
    	using std::cin;
    	
    	std::string s;
    
    	cout << "Enter string (Enter 'quit' to quit): ";
    	std::getline(cin, s);
    	while (s != "quit")
    	{
    		if (isPalindrome(s))
    			cout << "Yes, it is a palindrome.\n";
    		else
    			cout << "No, it is not a palindrome.\n";
    
    		cout << "Enter string. ('quit' to quit.): ";
    		std::getline(cin, s);
    	}
    
    	return 0;
    }
    
    bool isPalindrome(const std::string& s)
    {
    	int i = 0;
    	int j = s.length() - 1;
    
    	while (i < j)
    	{
    		if (!std::isalpha(s[i]))
    		{
    			++i;
    			continue;
    		}
    		if (!std::isalpha(s[j]))
    		{
    			--j;
    			continue;
    		}
    		if (std::tolower(s[i++]) != std::tolower(s[j--]))
    			return false;
    	}
    
    	return true;
    }
    Code:
    bool isPalindrome(const std::string& s)
    {
    	int i;
    	std::string original;
    	std::string reversed;
    
    	for (i = 0; i < s.length(); ++i)
    	{
    		if (std::isalpha(s[i]))
    		original += std::tolower(s[i]);
    	}
    	for (i = s.length()-1; i >= 0; --i)
    	{
    		if (std::isalpha(s[i]))
    		reversed += std::tolower(s[i]);
    	}
        
    	if (original == reversed)
    		return true;
    	else
    		return false;
    }

  2. #2
    Registered User
    Join Date
    May 2008
    Posts
    15
    Here's an alternative way to do it.

    Code:
    #include <iostream>
    #include <functional>
    #include <string>
    #include <algorithm>
    
    bool cic(char c1, char c2) { return tolower(c1) == tolower(c2); }
    
    bool is_palindrome(std::string s)
    {
        s.erase(
            std::remove_if(s.begin(), s.end(),
                std::not1(std::ptr_fun((isalpha)))
            ),
            s.end()
        );
    
        return std::equal(s.begin(), s.begin()+s.length()/2, s.rbegin(), cic);
    }
    
    int main()
    {
        std::cout << std::boolalpha << is_palindrome("Madam, I'm Adam") << std::endl;
        return 0;
    }

  3. #3
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    > Please tell me which one is better,
    Better how?
    - easiest to read
    - fastest
    - smallest code size
    - smallest data size
    - gets the most marks from the tutor
    - "cleverest" code (lots of hard to understand tricks - AVOID!).

    FWIW, both would be good answers in the absence of additional requirements.

    > and if there are better ones.
    Yes, when you've defined "better".
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  4. #4
    Registered User
    Join Date
    Aug 2009
    Posts
    3
    Thank you, rt454. I appreciate your help

    Well, what I meant by "better" is the fastest. Also, I want the code to be shorter. I somehow don't feel comfortable with the similar if & for statements. Thank you

  5. #5
    The larch
    Join Date
    May 2006
    Posts
    3,573
    In a program like you have, speed doesn't matter at all. However, if you needed to check lots and lots of palindromes, it would be probably better to use something that does not make a copy of the string. (Especially since you normally need to look at a couple of characters to determine that a string is not a palindrome.)

    I somehow don't feel comfortable with the similar if & for statements.
    I won't give a 100% guarantee, but this one here should do away with that, relying on short-circuiting of boolean expressions. I also think there are no sequence point issues. If you want, you can tack the inner if condition on to the outer condition as well.

    Code:
    bool isPalindrome(const std::string& s)
    {
        int i = 0;
        int j = s.length() - 1;
    
        while (i < j)
        {
            if (!((!std::isalpha(s[i]) && ++i) || (!std::isalpha(s[j]) && j--)))
                if (std::tolower(s[i++]) != std::tolower(s[j--]))
                    return false;
        }
        return true;
    }
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  6. #6
    Registered User
    Join Date
    Aug 2009
    Posts
    3
    I see your point ,anon. Thank you very much

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Buidl Library with ./configure script
    By Jardon in forum C Programming
    Replies: 6
    Last Post: 07-24-2009, 09:36 AM
  2. Profiler Valgrind
    By afflictedd2 in forum C++ Programming
    Replies: 4
    Last Post: 07-18-2008, 09:38 AM
  3. Interpreter.c
    By moussa in forum C Programming
    Replies: 4
    Last Post: 05-28-2008, 05:59 PM
  4. Problems about gcc installation
    By kevin_cat in forum Linux Programming
    Replies: 4
    Last Post: 08-09-2005, 09:05 AM
  5. Palindrome Coding trouble
    By TheLoneWolf32 in forum C++ Programming
    Replies: 3
    Last Post: 02-22-2003, 07:05 PM