Search code examples
javaarraysstringcharanagram

Determine if two words are anagrams


I recently took a quiz asking me to determine if elements in an array were anagrams. I completed an implementation, but upon running their tests, I only passed 1 of 5 test cases. The problem is, they wouldn't allow me to see what the tests were, so I'm really unsure about what I failed on. I've recreated my answer below, which basically multiplies the letters in a word and adds this number to an array. It then compares the numbers in one array to the numbers in the other, and prints true if they are the same. I'm basically asking what are some scenarios in which this would fail, and how would I modify this code to account for these cases?

public class anagramFinder {
    public static void main (String[] args){
        String[] listOne = new String[5];
        listOne[0] = "hello";
        listOne[1] = "lemon";
        listOne[2] = "cheese";
        listOne[3] = "man";
        listOne[4] = "touch";

        String[] listTwo = new String[5];
        listTwo[0] = "olleh";
        listTwo[1] = "melon";
        listTwo[2] = "house";
        listTwo[3] = "namer";
        listTwo[4] = "tou";

        isAnagram(listOne,listTwo);
    }

    public static void isAnagram(String[] firstWords, String[] secondWords){
        int firstTotal = 1;
        int secondTotal = 1;
        int[] theFirstInts = new int[firstWords.length];
        int[] theSecondInts = new int[secondWords.length];

        for(int i = 0;i<firstWords.length;i++){
            for(int j = 0;j<firstWords[i].length();j++){
                firstTotal = firstTotal * firstWords[i].charAt(j);
            }

            theFirstInts[i] = firstTotal;
            firstTotal = 1;
        }

        for(int i = 0;i<secondWords.length;i++){
            for(int j = 0;j<secondWords[i].length();j++){
                secondTotal = secondTotal * secondWords[i].charAt(j);
            }

            theSecondInts[i] = secondTotal;
            secondTotal = 1;
        }

        for(int i=0;i<minimum(theFirstInts.length,theSecondInts.length);i++){
            if(theFirstInts[i] == theSecondInts[i]){
                System.out.println("True");
            } else {
                System.out.println("False");
            }
        }
    }
    public static int minimum(int number,int otherNumber){
        if(number<otherNumber){
            return number;
        } else {
            return otherNumber;   
        }
    }
}

In my above example that I run in the main method, this prints True True False False False, which is correct


Solution

  • The idea of multiplying ASCII codes isn't bad, but not perfect. It would need a deep analysis to show that two different words could have the same products, with the given range of 'a' to 'z', and within reasonable length.

    One conventional approach would be to create a Map for counting the letters, and compare the Maps.

    Another one would sort the letters and compare the sorted strings.

    A third one would iterate over the letters of the first word, try to locate the letter in the second word, and reduce the second word by that letter.

    I can't think of a fourth way, but I'm almost certain there is one ;-)

    Later

    Well, here's a fourth way: assign 26 prime numbers to 'a' to 'z' and (using BigInteger) multiply the primes according to the letters of a word. Anagrams produce identical products.