ISC Practicals and Theory - Palindrome Word/Sentence

This program reads a sentence ending in a full stop, question mark or exclamation mark. It prints every word that is a palindrome, the number of such words, and whether the whole sentence is itself a palindrome. The words are cut out of the sentence with charAt() and substring(), without split() or StringTokenizer. Everything is written in the main method.

Definition

A palindrome reads the same from left to right and from right to left, e.g. Madam, level, a.

• Word level: Nitin is a palindrome (N-i-t-i-n against n-i-t-i-N, ignoring case); ran is not. A word of one letter, like a or I, is a palindrome.
• Sentence level: ignoring spaces, the terminator and case, Never odd or even. becomes neveroddoreven, which reads the same both ways, so the sentence is a palindrome (though none of its words is).

Choices made in this program:

• Spaces at the two ends of the line are ignored: the program removes them with trim(). The sentence is then valid only if its last character is ., ? or ! and at least one character comes before it. Anything else prints INVALID INPUT.
• Words are separated by spaces only, and any other character (a comma, for example) is treated as part of the word. For the whole-sentence test only spaces and the final terminator are ignored.
• Characters are compared case-insensitively by turning small letters into capitals with ASCII arithmetic, not with equalsIgnoreCase() or toLowerCase(). No library method that reverses a string is used.
• Single-letter words are counted as palindromes.
• A sentence made only of the terminator (.) has no words, so it is INVALID INPUT.

Algorithm

1. Read the sentence into str and remove the spaces at its two ends with trim(). It is valid only if it has at least 2 characters and ends in ., ? or !; otherwise print INVALID INPUT and stop.
2. Set result = "" and count = 0, and let n be the position of the terminator (str.length() - 1).
3. Cut out the words: with i from 0, skip a space; otherwise j moves to the end of the word, and w = str.substring(i, j) is the word. Then continue from i = j.
4. Test each word w with two pointers, a from the left end and b from the right end. Both characters are brought to capitals (a small letter has its ASCII value reduced by 32) so that the case is ignored. If any pair differs, set pal = false. A one-letter word is a palindrome.
5. If pal is true, add the word and a space to result and add 1 to count.
6. Print the palindrome words (or none) and count.
7. To test the whole sentence, move i from the left end and j from the right end (before the terminator). A space on either side is skipped; the other characters are compared, ignoring the case, and spal becomes false at the first difference. Print whether the sentence is a palindrome.

Program

In main, the first while loop cuts out the words and tests each with two pointers; the last while loop tests the whole sentence in the same way, skipping spaces.

import java.util.Scanner;

/* Program PalindromeWords reads a sentence, displays the words that are palindromes
   and checks whether the whole sentence is one. */
public class PalindromeWords
{
    public static void main(String args[])
    {
        Scanner sc = new Scanner(System.in);
        System.out.print("Enter a sentence: ");
        String str = sc.nextLine().trim();       // trim() removes the spaces at the two ends
        int n = str.length();
        boolean valid = false;                   // true if there is a word and a terminator . ? or !
        if (n >= 2)                              // empty, or only a terminator, is invalid
        {
            char last = str.charAt(n - 1);
            valid = last == '.' || last == '?' || last == '!';
        }
        if (!valid)
        {
            System.out.println("INVALID INPUT");
            return;
        }
        String result = "";                      // the palindrome words found, each followed by a space
        int count = 0;                           // number of palindrome words found
        n = n - 1;                               // position of the terminator
        int i = 0;
        while (i < n)
        {
            if (str.charAt(i) == ' ')            // skip spaces between words
                i++;
            else
            {
                int j = i;                       // j will stop just after the word
                while (j < n && str.charAt(j) != ' ')
                    j++;
                String w = str.substring(i, j);  // the word
                boolean pal = true;              // stays true if the word reads the same both ways
                int a = 0;                       // moves from the left end of the word
                int b = w.length() - 1;          // moves from the right end of the word
                while (a < b)
                {
                    char x = w.charAt(a), y = w.charAt(b);
                    if (x >= 'a' && x <= 'z')    // bring small letters to capitals to ignore the case
                        x = (char) (x - 32);
                    if (y >= 'a' && y <= 'z')
                        y = (char) (y - 32);
                    if (x != y)
                        pal = false;             // a mismatch: not a palindrome
                    a++;
                    b--;
                }
                if (pal)
                {
                    result = result + w + " ";
                    count++;
                }
                i = j;                           // continue after this word
            }
        }
        if (count == 0)
            System.out.println("Palindrome words: none");
        else
            System.out.println("Palindrome words: " + result);
        System.out.println("Number of palindrome words = " + count);
        // the whole sentence: ignoring spaces and case, it must read the same from both ends
        boolean spal = true;                     // stays true if the sentence is a palindrome
        i = 0;                                   // moves from the left end
        int j = str.length() - 2;                // moves from the right, before the terminator
        while (i < j)
        {
            if (str.charAt(i) == ' ')
                i++;                             // skip a space on the left
            else if (str.charAt(j) == ' ')
                j--;                             // skip a space on the right
            else
            {
                char x = str.charAt(i), y = str.charAt(j);
                if (x >= 'a' && x <= 'z')
                    x = (char) (x - 32);
                if (y >= 'a' && y <= 'z')
                    y = (char) (y - 32);
                if (x != y)
                    spal = false;
                i++;
                j--;
            }
        }
        if (spal)
            System.out.println("The sentence is a palindrome");
        else
            System.out.println("The sentence is not a palindrome");
    }
}

Variable description table

Sample input and output

Enter a sentence: Nitin ran.
Palindrome words: Nitin 
Number of palindrome words = 1
The sentence is not a palindrome

Enter a sentence: Never odd or even.
Palindrome words: none
Number of palindrome words = 0
The sentence is a palindrome

Enter a sentence:   I   am   not  a  Bob?
Palindrome words: I a Bob 
Number of palindrome words = 3
The sentence is not a palindrome

Enter a sentence: Madam
INVALID INPUT

Enter a sentence: .
INVALID INPUT

Enter a sentence:  Nitin ran.   
Palindrome words: Nitin 
Number of palindrome words = 1
The sentence is not a palindrome

Dry run

Input Nitin ran. (10 characters, so the terminator is at position 9 and n = 9). result is empty and count is 0.

So the output is Palindrome words: Nitin and Number of palindrome words = 1.

For the whole sentence, i = 0 and j = 8. N and n match (case ignored), so i = 1 and j = 7. Now i and a differ, so spal becomes false and the program prints The sentence is not a palindrome. This is the same as the real run above.

Variations

1. Palindrome String "Write a program to check whether a string is a palindrome using recursive technique." See Palindrome String; this note uses a loop, not recursion.
2. Reverse the words "Write a program to accept a sentence and print its words in reverse order."
3. Palindrome word "Write a program to accept a word and check whether it is a palindrome."
4. Longest palindrome word "Write a program to accept a sentence and print the longest palindrome word in it."