Code that checks if two words are anagrams

Question

I've completed a program that tests whether two words are anagrams. The program seems to work, but I was just wondering if there is anything I could be doing to make the code better. Everything is below, there is a main program and one class.

Main:

import java.util.Scanner; 

public class StringTesting
{
    public static void main(String[] args)
    {
        Scanner input = new Scanner(System.in);
        StringUtil object = new StringUtil();

        String word1;
        String word2;

        System.out.print("Enter word one: ");
        word1 = input.next();

        System.out.print("Enter word two: ");
        word2 = input.next();

        if(object.isAnagram(word1, word2)){
            System.out.println("It's an anagram!");
        } else {
            System.out.println("It's not an anagram.");
        }
    }
}

StringUtil Class:

public class StringUtil
{
    public int countCharacters(String str, char ch)
    {
        int count = 0; 

        for(byte i = 0; i < str.length(); i++){
            if(str.toLowerCase().charAt(i) == Character.toLowerCase(ch)){
                count++;
            }
        }

        return count; 
    }

    public boolean isAnagram(String str1, String str2)
    {
        int count = 0;

        if(str1.length() != str2.length()){
            return false;
        }

        for(byte i = 0; i < str1.length(); i++){
            char ch = str1.toLowerCase().charAt(i);
            for(byte j = 0; j < str1.length(); j++){
                char ch2 = str2.toLowerCase().charAt(j);
                if(ch == ch2){
                    if(countCharacters(str1, ch) != countCharacters(str2, ch2)){
                        return false;
                    } else {
                        count++;
                    } 
                }
            }
        }

        if(count == str1.length()){
            return true; 
        } else {
            return false;   
        } 
    }
} 

Answer 1

The algorithm in isAnagram is far from being efficient.

Consider two strings: each is a letter "a" repeated 1000 times. We will count the occurrences of 'a' in both strings 1000 times - each time getting the same answer. In other words, the worst case complexity is O(len(input)^2).

It's possible to cache the number of occurrences of a given character in a Map while retaining the rest of your current algorithm. This would speed up most cases, but the worst case complexity will still be O(len(input)^2) (consider an anagram where no letter occurs twice, and is a reverse of the first string).

What we could do is something like this:

1. Iterate once through each string to create a HashMap with the count of each character's occurrences.
2. If the two maps are equal, we have an anagram. Otherwise, we don't.

The complexity would be O(len(input1) + len(input2)).

Answer 2

The easiest solution IMO is to sort the strings and compare them.

public String sort(String s) {
  char[] c = s.toLowerCase().toCharArray();
  Arrays.sort(c);
  return new String(c);
}

public boolean isAnagram(String a, String b) {
  return sort(a).equals(sort(b));
}

Answer 3

The algorithm is inefficient as stated by RomanK.

Considering that the program is case-insensitive, we could declare a couple of arrays to keep track of the letters in the words.

int[] countOfCharactersInFirstWord = new int[26];
int[] countOfCharactersInSecondWord = new int[26];

We can iterate the words and use the following logic.

for(char ch : firstWord.toCharArray()) {
    char lowercaseLetter = Character.toLowerCase(ch);
    int index = lowerCaseLetter - 97; // 97 is ASCII value of 'a'
    countOfCharactersInFirstWord[index]++;
}

We can follow the aforementioned logic for the second word too and then compare the count of the letters in both the arrays. If they don't match, return false.

You have created a class with a main method in order to test this program. I suggest you use JUnit or any other testing framework to test your programs. It is a good practice to follow right from the start.