ISC Practicals and Theory - Anagram (OOP)

Two words or phrases are anagrams if they use the same letters the same number of times. This version is written as a class with a parameterised constructor: main reads the two lines and passes them to the constructor, and separate methods fill the two frequency arrays, compare them and print the result.

Definition

Two strings are anagrams if they contain exactly the same letters with the same frequencies. This program ignores case, spaces and non-letters. A line with no letters at all (for example 123) has nothing to rearrange, so it gives NOT ANAGRAMS. Listen and Silent are anagrams, and so are Dormitory and Dirty room; Hello and Helo are not, since l occurs twice in one and once in the other.

Algorithm

1. main reads the two lines into x and y. If either is empty, it prints INVALID INPUT and stops.
2. Otherwise main creates ob = new Anagram(x, y). The constructor stores the strings in a and b and creates fa[] and fb[], 26 elements each, all 0.
3. fill() calls count(a, fa) and count(b, fb).
4. count(s, f) visits each character ch of s. A capital letter has 32 added to it. If the result is between 'a' and 'z', f[ch - 'a'] is increased by 1; other characters are ignored.
5. display() calls isAnagram(). It returns false at once if hasLetter(fa) or hasLetter(fb) is false (a string with no letters); otherwise it compares fa[i] and fb[i] for i from 0 to 25 and returns false at the first difference, or true if none. display() prints ANAGRAMS or NOT ANAGRAMS.

Program

Compared with the plain version, the strings come in through the parameterised constructor Anagram(String x, String y), there is no accept() method, and filling the frequency arrays has its own method fill(). The method hasLetter() tells whether a frequency table has any letter.

import java.util.Scanner;

/* Class Anagram (OOP version): the two strings are given to the constructor.
   They are anagrams if they have the same letters with the same frequencies;
   case, spaces and non-letters are ignored. */
public class Anagram
{
    String a;       // stores the first word or phrase
    String b;       // stores the second word or phrase
    int fa[];       // letter frequencies of a: fa[0] for 'a' ... fa[25] for 'z'
    int fb[];       // letter frequencies of b

    /* Parameterised constructor. Parameters: x is the first string and y is
       the second string. Stores them and creates the two frequency arrays
       (all counts 0). */
    Anagram(String x, String y)
    {
        a = x;
        b = y;
        fa = new int[26];
        fb = new int[26];
    }

    /* Parameters: s is the string to be examined and f is the frequency
       array to be filled. Adds 1 to f for every letter of s, using
       character arithmetic (no Character.isLetter() or toLowerCase()). */
    void count(String s, int f[])
    {
        int i;
        char ch;
        for (i = 0; i < s.length(); i++)       // visit every character
        {
            ch = s.charAt(i);
            if (ch >= 'A' && ch <= 'Z')        // capital: bring to the small-letter range
                ch = (char)(ch + 32);
            if (ch >= 'a' && ch <= 'z')        // ignore spaces, digits, punctuation
                f[ch - 'a']++;                 // 'a' -> 0 ... 'z' -> 25
        }
    }

    /* Fills the frequency arrays of both strings */
    void fill()
    {
        count(a, fa);
        count(b, fb);
    }

    /* Parameter f: a frequency array. Returns true if at least one letter has
       been counted in it, otherwise false. */
    boolean hasLetter(int f[])
    {
        int i;
        for (i = 0; i < 26; i++)
        {
            if (f[i] > 0)
                return true;
        }
        return false;
    }

    /* Returns false if either string has no letter at all; otherwise compares
       fa[] and fb[] position by position and returns true if all 26 counts
       are equal, false if not. */
    boolean isAnagram()
    {
        int i;
        if (!hasLetter(fa) || !hasLetter(fb))   // a string without letters has nothing to rearrange
            return false;
        for (i = 0; i < 26; i++)
        {
            if (fa[i] != fb[i])                // one different count is enough to fail
                return false;
        }
        return true;
    }

    /* Prints ANAGRAMS or NOT ANAGRAMS */
    void display()
    {
        if (isAnagram())
            System.out.println("ANAGRAMS");
        else
            System.out.println("NOT ANAGRAMS");
    }

    /* main reads the two strings, rejects an empty line, creates the object
       with the strings and calls the methods. */
    public static void main(String args[])
    {
        Scanner sc = new Scanner(System.in);
        System.out.print("Enter the first word or phrase: ");
        String x = sc.nextLine();
        System.out.print("Enter the second word or phrase: ");
        String y = sc.nextLine();
        if (x.length() == 0 || y.length() == 0)    // an empty line is invalid
            System.out.println("INVALID INPUT");
        else
        {
            Anagram ob = new Anagram(x, y);        // object of class Anagram
            ob.fill();
            ob.display();
        }
    }
}

Variable description table

Sample input and output

Enter the first word or phrase: Listen
Enter the second word or phrase: Silent
ANAGRAMS

Enter the first word or phrase: Dormitory
Enter the second word or phrase: Dirty room
ANAGRAMS

Enter the first word or phrase: Hello
Enter the second word or phrase: Helo
NOT ANAGRAMS

Enter the first word or phrase: Hello
Enter the second word or phrase: Hello
ANAGRAMS

Enter the first word or phrase: 123
Enter the second word or phrase: ?!
NOT ANAGRAMS

Dry run

Input Hello and Helo. After fill() the non-zero counts are:

isAnagram() compares from index 0. Indices 0 to 10 are equal (0 and 0, except e and h which are 1 and 1). At index 11 (l), fa[11] is 2 and fb[11] is 1, so it returns false and display() prints NOT ANAGRAMS, the same as the real run above.

Variations

1. Pangram "Write a program to check whether a sentence contains every letter of the alphabet."
2. Letter frequency "Write a program to accept a sentence and print the frequency of each letter in it."
3. Isogram "Write a program to check whether a word has no repeated letter."