ISC Practicals and Theory - Longest and Shortest Word

This program reads a sentence and prints its longest word and its shortest word, each with its length. The words are picked out one character at a time with charAt(), substring() and length(); split() and StringTokenizer are not used. Everything is written in the main method.

Definition

A word here is a run of characters between spaces. The sentence must end with ., ? or !; that last character is the terminator and is not part of the last word. Extra spaces between words are skipped, and spaces at the two ends of the line are ignored.

• The quick brown fox jumps. has the words The, quick, brown, fox, jumps (lengths 3, 5, 5, 3, 5). The longest word is quick and the shortest is The.
• If two words have the same length, the program keeps the first one. So quick (not brown or jumps) is the longest, and The (not fox) is the shortest.
• A sentence of one word, such as Wonderful!, gives that word as both the longest and the shortest.

Algorithm

1. Read the sentence into sent and remove the spaces at its two ends with trim().
2. The sentence is valid only if it has at least 2 characters and its last character is ., ? or !. If not, print INVALID INPUT and stop.
3. Remove the terminator: text = sent.substring(0, n - 1). Set w = "", the word being formed.
4. Go through text with i from 0 to len (the index len acts as a space after the last word). A character that is not a space is added to w. A space after a word completes the word:
   • the first word is both the longest and the shortest, so store it in longest and shortest and its length in maxLen and minLen;
   • a later word replaces longest only if it is strictly longer than maxLen, and replaces shortest only if it is strictly shorter than minLen, so ties keep the first word;
   • then w is made empty for the next word.
5. Print the longest and the shortest word with their lengths.

Program

The single for loop in main builds one word at a time and compares its length with maxLen and minLen when the word is complete.

import java.util.Scanner;

/* Program WordLength reads a sentence and displays its longest and its shortest word
   without using split() or StringTokenizer. Ties go to the first word. */
public class WordLength
{
    public static void main(String args[])
    {
        Scanner sc = new Scanner(System.in);
        System.out.print("Enter a sentence: ");
        String sent = sc.nextLine().trim();      // trim() removes the spaces at the two ends
        int n = sent.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 = sent.charAt(n - 1);      // last character of the sentence
            valid = last == '.' || last == '?' || last == '!';
        }
        if (!valid)
        {
            System.out.println("INVALID INPUT");
            return;
        }
        String text = sent.substring(0, n - 1);  // terminator removed
        String longest = "", shortest = "";      // longest and shortest word found so far
        int maxLen = 0, minLen = 0;              // their lengths
        String w = "";                           // word being formed
        int len = text.length();
        for (int i = 0; i <= len; i++)           // i == len acts as a space after the last word
        {
            char ch = ' ';
            if (i < len)
                ch = text.charAt(i);
            if (ch != ' ')
                w = w + ch;                      // letter: add it to the current word
            else if (w.length() > 0)             // space after a word: the word is complete
            {
                if (longest.length() == 0)       // first word: it is both longest and shortest
                {
                    longest = w;
                    shortest = w;
                    maxLen = w.length();
                    minLen = w.length();
                }
                else
                {
                    if (w.length() > maxLen)     // strictly longer: ties keep the first word
                    {
                        longest = w;
                        maxLen = w.length();
                    }
                    if (w.length() < minLen)     // strictly shorter: ties keep the first word
                    {
                        shortest = w;
                        minLen = w.length();
                    }
                }
                w = "";                          // start the next word
            }
        }
        System.out.println("Longest word = " + longest + " (length " + maxLen + ")");
        System.out.println("Shortest word = " + shortest + " (length " + minLen + ")");
    }
}

Variable description table

Sample input and output

Enter a sentence: The quick brown fox jumps.
Longest word = quick (length 5)
Shortest word = The (length 3)

Enter a sentence:   Is   it a   big   cat ?
Longest word = big (length 3)
Shortest word = a (length 1)

Enter a sentence: Wonderful!
Longest word = Wonderful (length 9)
Shortest word = Wonderful (length 9)

Enter a sentence: Hello world
INVALID INPUT

Enter a sentence: .
INVALID INPUT

Enter a sentence: Wonderful!   
Longest word = Wonderful (length 9)
Shortest word = Wonderful (length 9)

Dry run

Input The quick brown fox jumps. After the terminator is removed, text is The quick brown fox jumps (length 25). Letters only grow w; the table shows the moments when a word is completed.

The program prints Longest word = quick (length 5) and Shortest word = The (length 3), the same as the real run above.

Variations

1. Last word on a tie "Write a program to find the longest and shortest word of a sentence; if two words have the same length, display the last one."
2. Count words "Write a program to count the number of words in a sentence."
3. Reverse each word "Write a program to reverse every word of a sentence, keeping the word order."