Skip to main content

Problem Solving with Algorithms and Data Structures using C++ The PreTeXt Interactive Edition

Section 3.18 Palindrome-Checker

An interesting problem that can be easily solved using the deque data structure is the classic palindrome problem. A palindrome is a string that reads the same forward and backward, for example, radar, toot, and madam. We would like to construct an algorithm to input a string of characters and check whether it is a palindrome.
🔗
The solution to this problem will use a deque to store the characters of the string. We will process the string from left to right and add each character to the rear of the deque. At this point, the deque will be acting very much like an ordinary queue. However, we can now make use of the dual functionality of the deque. The front of the deque will hold the first character of the string and the rear of the deque will hold the last character (see Figure 3.18.1).
🔗
described in detail following the image
The image depicts adding the word "radar" to a dequeue. Each character is added to the rear of the queue during initialization, when all the characters have been added character afters are removed from each end of the queue: R is removed from the rear and another R is removed from the head of the queue.
🔗
Figure 3.18.1. A Deque
🔗
Since we can remove both of them directly, we can compare them and continue only if they match. If we can keep matching first and the last items, we will eventually either run out of characters or be left with a deque of size 1 depending on whether the length of the original string was even or odd. In either case, the string must be a palindrome. The complete function for palindrome-checking appears in Task 3.18.1.a.
🔗

Exploration 3.18.1. Basic Palindrome Checker.

(a) C++ Implementation. 

//program that detects palindromes.

#include <deque>
#include <iostream>
#include <string>

using namespace std;

bool palchecker(string aString) {
    deque<char> chardeque;
    int strLen = aString.length();
    for (int i = 0; i < strLen; i++) {
        //pushes each char in the string to the deque.
        chardeque.push_back(aString[i]);
    }

    bool stillEqual = true;

    while (chardeque.size() > 1 && stillEqual) {
        char first = chardeque.front();
        chardeque.pop_front();
        char last = chardeque.back();
        chardeque.pop_back();
        if (first != last) { //if the two opposite positions of the
                             //word is not the same, then it is not
                             //a palindrome.
            stillEqual = false;
        }
    }
    return stillEqual;
}

int main() {
    cout << palchecker("lsdkjfskf") << endl;
    cout << palchecker("radar") << endl;
}
🔗

(b) Python Implementation.

🔗
🔗
Below we can see an upgraded code for checking palindromes, which is able to handle strings with capital letters, spaces, and special characters.
🔗
Listing 3.18.2. Advanced Palindrome Checker
🔗
//program that detects palindromes.

/*
The Advanced Palindrome Checker
By: David Reynoso and David Andrejsin
*/

using namespace std;
#include <deque>
#include <fstream> // for file handling
#include <iostream>
#include <string>
#include "stdlib.h" // for the system command
#include <algorithm> // provides an algorithm for easier removal of characters from a string

string processor(string aString) {
    // goes through string and finds uppercase letters and converts
    // them to lower case, also finds special characters and gets rid of them
    // ultimately, prepares a string for a correct palindrome evaluation
    int strLen = aString.length();
    string str = "";
    for (int i = 0; i < strLen; i++) {
        str += tolower(aString[i]);
    }
    str.erase(remove(str.begin(), str.end(), ' '), str.end());
    str.erase(remove(str.begin(), str.end(), '.'), str.end());
    str.erase(remove(str.begin(), str.end(), '?'), str.end());
    str.erase(remove(str.begin(), str.end(), '!'), str.end());
    str.erase(remove(str.begin(), str.end(), ','), str.end());
    str.erase(remove(str.begin(), str.end(), ';'), str.end());
    str.erase(remove(str.begin(), str.end(), ':'), str.end());
    str.erase(remove(str.begin(), str.end(), '#'), str.end());
    str.erase(remove(str.begin(), str.end(), '"'), str.end());
    str.erase(remove(str.begin(), str.end(), '\''), str.end());
    // we had to use a backslash to espace the function of '
    str.erase(remove(str.begin(), str.end(), '-'), str.end());
    str.erase(remove(str.begin(), str.end(), '('), str.end());
    str.erase(remove(str.begin(), str.end(), ')'), str.end());

    return str;
}

bool palchecker(string aString) {
    // an algorithm that checks whether a string is a palindrome
    aString = processor(aString); // calls a function that prepares the string for a proper evaluation of the palindrome

    deque<char> chardeque;
    int strLen = aString.length();
    for (int i = 0; i < strLen; i++) {
    //pushes each char in the string to the deque.
        chardeque.push_back(aString[i]);
    }

    bool stillEqual = true;

    while (chardeque.size() > 1 && stillEqual) {
        char first = chardeque.front();
        chardeque.pop_front();
        char last = chardeque.back();
        chardeque.pop_back();
        if (first != last) { //if the two opposite positions of the
             //word is not the same, then it is not
             //a palindrome.
            stillEqual = false;
        }
    }
    return stillEqual;
}

int main() {
    cout << palchecker("Radar") << endl;
    cout << palchecker("Are we not pure? 'No sir!' Panama's moody Noriega brags. 'It is garbage!' Irony dooms a man; a prisoner up to new era.") << endl;
    cout << palchecker("Barge in! Relate mere war of 1991 for a were-metal Ernie grab!") << endl;
    cout << palchecker("not a palindrome") << endl;
}

Reading Questions Reading Questions

1.

🔗

2.

🔗

3.

If you add five items to your code in this order “potato”, “rutabaga”, “avocado”, “squash”, “eggplant” which structure would take the least steps to retrieve “rutabaga”?
🔗
  • Deque
    🔗
  • Yes, but it is not the only option.
  • Stack
    🔗
  • No, a stack would pop from the top, thus having more entries in the way before it gets to rutabega.
  • Queue
    🔗
  • Yes, but it is not the only option.
  • Both B & C
    🔗
  • One of these two would be correct, but the other would not.
  • Both A & C
    🔗
  • Correct!
🔗
🔗
🔗
PrevTopNext