ISC Practicals and Theory - Palindrome String (Recursive Technique) (OOP)

This version checks whether a word is a palindrome using recursion, written as a class whose object is built with a parameterised constructor. The word is passed to the object when it is created, and each method does one job: test, store the answer, print.

Definition

A string is a palindrome if it reads the same from left to right and from right to left, for example racecar. A string of length 0 or 1 is always a palindrome, so a one-character word such as x is reported as a palindrome (checked by running the program). Capital and small letters are treated as equal because the constructor converts the word to lower case, so Aa is a palindrome.

The word is read with next(), so only the first word typed is tested (for "nurses run" only nurses is tested), and spaces and punctuation are not handled. An empty input cannot be tested: next() finds no word to read and the program stops with a NoSuchElementException.

Algorithm

1. main reads a word and creates the object ob with new PalindromeOOP(w). The constructor stores w.toLowerCase() in word and sets result to false.
2. check() calls isPalin(word) and keeps the answer in result.
3. isPalin(s) is the recursive method:
   • Find n, the length of s.
   • Base case: if n <= 1, return true.
   • If s.charAt(0) and s.charAt(n - 1) differ, return false.
   • Recursive case: return isPalin(s.substring(1, n - 1)), the same test without the first and last characters.
4. display() prints "is a Palindrome" if result is true, otherwise "is not a Palindrome".

Program

The class PalindromeOOP has two data members, a parameterised constructor, the recursive isPalin(), and the one-job methods check() and display(). main reads the word with Scanner, creates the object and calls the methods.

import java.util.Scanner;

/* Class PalindromeOOP checks recursively whether a word is a palindrome.
   The word is given to the constructor when the object is created. */
public class PalindromeOOP
{
    String word;       // the word to be tested (stored in lower case)
    boolean result;    // true if word is a palindrome, false otherwise

    /* Parameterised constructor. Parameter w: the word typed by the user.
       Stores it in lower case so that upper/lower case are treated alike. */
    PalindromeOOP(String w)
    {
        word = w.toLowerCase();
        result = false;
    }

    /* Recursive method. Parameter s: the part of the word still to be checked.
       Returns true if s is a palindrome, otherwise false. */
    boolean isPalin(String s)
    {
        int n = s.length();        // length of the current string
        if (n <= 1)                // base case: nothing left to compare
            return true;
        if (s.charAt(0) != s.charAt(n - 1))   // end characters differ
            return false;
        return isPalin(s.substring(1, n - 1)); // recursive case: remove both ends
    }

    /* Calls isPalin() on the stored word and keeps the answer in result */
    void check()
    {
        result = isPalin(word);
    }

    /* Prints the message according to the value of result */
    void display()
    {
        if (result)
            System.out.println(word + " is a Palindrome");
        else
            System.out.println(word + " is not a Palindrome");
    }

    /* main reads the word, creates the object and calls the methods */
    public static void main(String args[])
    {
        Scanner sc = new Scanner(System.in);   // reads input from the keyboard
        System.out.print("Enter a word: ");
        String w = sc.next();                  // word typed by the user
        PalindromeOOP ob = new PalindromeOOP(w);  // object of the class
        ob.check();
        ob.display();
    }
}

Variable description table

Sample input and output

Enter a word: Racecar
racecar is a Palindrome

Enter a word: Abca
abca is not a Palindrome

Enter a word: x
x is a Palindrome

Dry run

Input Racecar. The constructor stores word = racecar; check() calls isPalin("racecar").

result becomes true, and display() prints racecar is a Palindrome, the same as the real run above.

Variations

1. Palindrome sentence "Write a program to check whether a sentence is a palindrome, ignoring spaces and punctuation."
2. Reverse a string "Write a program to reverse a string using recursive technique."