DS Palindrome Checker

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 tail 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 head of the deque will hold the first character of the string and the tail of the deque will hold the last character (see Figure 3.18.1).

Figure 3.18.1. A Deque for Palindrome Checking

Since we can remove both of the head and tail characters 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 method for palindrome-checking appears in Listing 3.18.2.

import java.util.ArrayList;
import java.util.NoSuchElementException;
import java.util.ArrayList;
import java.util.NoSuchElementException;

class Deque<T> {

ArrayList<T> items;

public Deque() {
        this.items = new ArrayList<T>();
    }

public boolean isEmpty() {
        return (this.items.isEmpty());
    }

public void addHead(T item) {
        this.items.add(item);
    }

public void addTail(T item) {
        this.items.add(0, item);
    }

public T removeHead() {
        if (this.isEmpty()) {
            throw new NoSuchElementException("Deque is empty.");
        }
        return this.items.remove(this.size() - 1);
    }

public T removeTail() {
        if (this.isEmpty()) {
            throw new NoSuchElementException("Deque is empty.");
        }
        return this.items.remove(0);
    }

public T peekHead() {
        if (this.isEmpty()) {
            throw new NoSuchElementException("Deque is empty.");
        }
        return this.items.get(this.size() - 1);
    }

public T peekTail() {
        if (this.isEmpty()) {
            throw new NoSuchElementException("Deque is empty.");
        }
        return this.items.get(0);
    }

public int size() {
        return this.items.size();
    }

public String toString() {
        if (!this.items.isEmpty()) {
            String arrString = this.items.toString();
            return "tail " + arrString + " head";
        } else {
            return "<<empty deque>>";
        }
    }
}

^^^^
public class Palindrome {

public static boolean isPalindrome(String str) {
        Deque<Character> charDeque = new Deque<Character>();

for (int i = 0; i < str.length(); i++) {
            charDeque.addTail(str.charAt(i));
        }

while (charDeque.size() > 1) {
            Character first = charDeque.removeHead();
            Character last = charDeque.removeTail();
            if (!first.equals(last)) {
                return false;
            }
        }
        return true;
    }

public static void main(String[] args) {
        System.out.println("Is \"regular\" a palindrome? " +
            isPalindrome("regular"));
        System.out.println("Is \"rotator\" a palindrome? " +
            isPalindrome("rotator"));
        System.out.println("Is \"deed\" a palindrome? " +
            isPalindrome("deed"));
    }
}

Listing 3.18.2. Implementation of Palindrome Checker

Note 3.18.3.

If you want to have a double quote appear in a double-quoted string, you must escape it by using the backslash before the internal double quotes.

The test program checks to see that words with an odd number of letters (rotator) and an even number of letters (deed) are handled correctly.

You have attempted of activities on this page.

Prev Top Next