Exercise 5-10

Palindromes are words that are spelled the same right to left as left to right. Write a program to find all the palindromes in a dictionary. Next, find the longest palindrome.

Solution

Just a bit of disclosure before moving on. In chapter 6 (i.e. the next chapter) the author will introduce a more compact technique to auto detect palindromes. In this post however, I shall build up the solution using only the knowledge we have learnt so far (up to chapter 5). I believe the author is trying to build up the grounds before introducing new C++ techniques.

The solution strategy:

1. As usual, have a means to read in words – using the while / cin / push_back method.
2. Have a home-made function isPalindrome that takes in a string and do the “magic” – return (bool type) true if the string is a palindrome.
3. Have a home-made function lowcase to convert all the letters of a word to lower case. This is to aid the letter comparison process within the isPalindrome function.
4. Have a home-made findLongest function to determine the longest (string) palindrome,
5. Re-use the home-made vcout function to display the string elements witin a vector<string> container. e.g. the vector containing the palindromes.

The isPalindrome Algorithm

A palindrome is a word that read the same in both directions. This function essentially require two iterators a and b, in which iterator a start from the first to last letter of the word, whereas iterator b (is vice versa, ) start from the last to the first of the word. The function compare the two underlying letters regardless of case. (To do this I have a home-made lowcase function that will convert all the letters to lower case first prior the comparing – the lowcase function is very simple, rather than explaining in-depth here, just look at the code lowcase.cpp under the Project section.). The following diagram summarise the isPalindrome function logic.

See the Project section for the full code for isPalindrome.

The Project

Wrapping up all the source and header files here all in one place.

Source File List

• main.cpp
• findLongest.cpp
• isPalindrome.cpp
• lowcase.cpp
• vcout.cpp

Header File List

• findLongest.h
• isPalindrome.h
• lowcase.h
• vcout.h

Source Files

main.cpp

#include <iostream>  // cin, cout, endl
#include <string>
#include <vector>
#include "vcout.h"  // vcout
#include "isPalindrome.h"   // isPalindrome
#include "findLongest.h"   // findLongest

using std::cin;
using std::cout;
using std::endl;
using std::string;
using std::vector;

int main()
{
  string word;
  vector<string> words;
  vector<string> palindromes;

  // Populate vector
  while (cin >> word) {
    if (isPalindrome(word))
      palindromes.push_back(word);
  }

  // Print palindrome
  cout << "\nThese are the palindromes identified: " << endl;
  vcout(palindromes);

  // Print longest palindrome (take first observed)
  cout << "\nThe (first observed) longest palindrome is:\n"
       << findLongest(palindromes) << endl;

  return 0;
}

findLongest.cpp

#include <string>
#include <vector>

using std::string;
using std::vector;

string findLongest(const vector<string>& words)
{
  string longestWord;
  for (vector<string>::const_iterator i = words.begin(); i != words.end(); ++i) {
    if ( i->size() > longestWord.size() )
      longestWord = *i;
  }
  return longestWord;
}

isPalindrome.cpp

#include <string>
#include "lowcase.h"

using std::string;

bool isPalindrome(const string& s)
{

  string word = lowcase(s);

  string::const_iterator a = word.begin();
  string::const_iterator b = word.end() - 1;

  while ( a <= b && a != word.end()) {
    if ( *a != *b )
      return false;
    ++a;
    --b;
  }
  return true;
}

lowcase.cpp

#include <string>
#include <cctype>

using std::string;
using std::tolower;

string lowcase(const string& s)
{
    string ret;
    for (string::size_type i = 0; i != s.size(); ++i)
    {
        ret.push_back(tolower(s[i]));
    }
    return ret;
}

vcout.cpp

#include <iostream>
#include <string>    // string
#include <vector>    // vector

using std::cout;
using std::endl;
using std::string;
using std::vector;

int vcout(const vector<string>& v)
{
    for (vector<string>::const_iterator iter = v.begin();
         iter != v.end(); ++iter)
    {
        cout << (*iter) << endl;
    }
    return 0;
}

Header Files

findLongest.h

#ifndef GUARD_FINDLONGEST_H
#define GUARD_FINDLONGEST_H

#include <string>
#include <vector>

std::string findLongest(const std::vector<std::string>&);

#endif // GUARD_FINDLONGEST_H

isPalindrome.h

#ifndef GUARD_ISPALINDROME_H
#define GUARD_ISPALINDROME_H

#include <string>

bool isPalindrome(const std::string&);

#endif // GUARD_ISPALINDROME_H

lowcase.h

#ifndef GUARD_LOWCASE_H
#define GUARD_LOWCASE_H

#include <string>

std::string lowcase(const std::string&);

#endif // GUARD_LOWCASE_H

vcout.h

#ifndef GUARD_VCOUT_H
#define GUARD_VCOUT_H

#include <string>
#include <vector>

int vcout(const std::vector<std::string>&);

#endif // GUARD_VCOUT_H

Test Program

The program allows us to enter a list of words, and automatically display the palindromes (if any), followed by the longest palindrome.

bib good Morning bob dad Abba
Hello Deed Civic Solos
Redder Kelly DEIfied rOtaToR
^Z

These are the palindromes identified:
bib
bob
dad
Abba
Deed
Civic
Solos
Redder
DEIfied
rOtaToR

The (first observed) longest palindrome is:
DEIfied

As expected, the determination of palindromes is regardless of upper / lower case letters.

Further Readings

Purely out of curosity, palindrome applies not only to words, but also to phrases. For instance, the following phrases read the same in both direction.

(Reference: http://www.highlightpress.com.au/list-of-palindromes.html)

• Able I was ere I saw Elba
• Ah, Satan sees Natasha
• A man, a plan, a canal: Panama
• Do geese see God?
• Live not on evil
• Murder for a jar of red rum
• Never odd or even
• No, it is opposition

What about, to write a C++ program to determine palindrome sentences? That would be interesting.

I guess the algorithm would be just a matter of:

1. Using the standard C++ getline function to read and parse in the whole sentences instead of just words.
2. Removing all the special characters such as punctuations and empty spaces within the sentences.
3. Converting all letters to lower cases.
4. Applying the isPalindrome function against the newly formatted sentences. (i.e. treat the formatted sentences as “words”)

Something for later maybe!

Reference

Koenig, Andrew & Moo, Barbara E., Accelerated C++, Addison-Wesley, 2000