ISC Practicals and Theory - Anagram

Two words or phrases are anagrams if one can be made by rearranging the letters of the other. This program, written in the main method alone, reads two lines, counts how many times each letter occurs in each of them using two int arrays of size 26, and compares the two arrays position by position.

Definition

Two strings are anagrams if they contain exactly the same letters with exactly the same frequencies. This program ignores case, spaces and every character that is not a letter.

• Listen and Silent are anagrams: both have e, i, l, n, s, t once each.
• Dormitory and Dirty room are anagrams: d, i, m, t, y once, o and r twice in both. The space is ignored.
• Hello and Helo are not: l occurs twice in the first and once in the second.
• Identical strings such as Hello and Hello are anagrams of each other, since the letters and counts are the same.
• A line with no letters at all (for example 123 or ?!) has nothing to rearrange, so such a pair gives NOT ANAGRAMS.

Algorithm

1. Read the two lines into a and b. If either is empty, print INVALID INPUT and stop.
2. Create two arrays fa and fb of size 26, all 0. fa[0] counts the letter a in a, fa[1] counts b, and so on up to fa[25] for z.
3. Visit every character ch of a. If it is a capital letter, add 32 to bring it to the small-letter range. If it is now between 'a' and 'z', add 1 to fa[ch - 'a']. Spaces, digits and punctuation marks are ignored. No Character.isLetter() or toLowerCase() is used, only character arithmetic.
4. Do the same for b and fb.
5. For every index i from 0 to 25, note whether fa[i] or fb[i] is above 0 (hasA, hasB), and set same = false if fa[i] != fb[i]. One different count is enough to fail.
6. If both lines have at least one letter and same is still true, print ANAGRAMS. Otherwise print NOT ANAGRAMS.

Program

The two for loops in main fill the frequency tables, and a third loop compares them.

import java.util.Scanner;

/* Program Anagram checks whether two words or phrases are anagrams: they
   use exactly the same letters with the same frequencies. Case, spaces and
   all non-letters are ignored. */
public class Anagram
{
    public static void main(String args[])
    {
        Scanner sc = new Scanner(System.in);
        System.out.print("Enter the first word or phrase: ");
        String a = sc.nextLine();                  // the first word or phrase
        System.out.print("Enter the second word or phrase: ");
        String b = sc.nextLine();                  // the second word or phrase
        if (a.length() == 0 || b.length() == 0)
        {
            System.out.println("INVALID INPUT");
            return;
        }
        int fa[] = new int[26];     // fa[0] counts 'a' in a, fa[1] counts 'b' ... fa[25] counts 'z'
        int fb[] = new int[26];     // same frequency table for the second string b
        int i;
        char ch;
        for (i = 0; i < a.length(); i++)           // visit every character of a
        {
            ch = a.charAt(i);
            if (ch >= 'A' && ch <= 'Z')            // capital letter: bring it to the small-letter range
                ch = (char) (ch + 32);
            if (ch >= 'a' && ch <= 'z')            // spaces, digits and punctuation are ignored
                fa[ch - 'a']++;                    // 'a' -> 0 ... 'z' -> 25
        }
        for (i = 0; i < b.length(); i++)           // visit every character of b
        {
            ch = b.charAt(i);
            if (ch >= 'A' && ch <= 'Z')
                ch = (char) (ch + 32);
            if (ch >= 'a' && ch <= 'z')
                fb[ch - 'a']++;
        }
        boolean hasA = false, hasB = false;        // does a (or b) contain at least one letter?
        boolean same = true;                       // stays true while all counts are equal
        for (i = 0; i < 26; i++)
        {
            if (fa[i] > 0)
                hasA = true;
            if (fb[i] > 0)
                hasB = true;
            if (fa[i] != fb[i])                    // one different count is enough to fail
                same = false;
        }
        if (hasA && hasB && same)                  // a line without letters has nothing to rearrange
            System.out.println("ANAGRAMS");
        else
            System.out.println("NOT ANAGRAMS");
    }
}

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. The counting loops fill the tables below (letters not listed have count 0).

The last loop compares from index 0. Indices 0 to 3 are 0 and 0, index 4 (e) is 1 and 1, indices 5 and 6 are equal, index 7 (h) is 1 and 1, and indices 8 to 10 are equal. At index 11 (l), fa[11] is 2 and fb[11] is 1, which differ, so same becomes false and the program prints NOT ANAGRAMS. This is 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."