Java anagram finder algorithm

Question

I have an array of Strings in Java. I need to find anagrams from the array and print them to the screen.

I am having difficulty with the part where I am supposed to compare array elements to check if they're anagrams or not. How would I do this? I would have to make a loop to go through the array obviously.

I think that I could sort the Strings and then compare them (since if they're anagrams, they would contain the same letters in the same order when sorted), but how would I unsort them to get the original word?

score 4 · Answer 1 · answered Feb 17 '12 at 01:29

If you alphabetize the letters than hash them, they should be the same...

Map<String, List<String>> words = new HashMap<String, List<String>>();
for(String word : incomingWords) {
   final String key = alphabetize(word);
   if(words.contains(key)){
      words.get(key).add(word);
   } else {
      words.put(key, new ArrayList<String>());
      words.get(key).add(word);
   }
}

Now you have Map of words that are anagrams... You will also have Lists in the Map that only have 1 entry, you can remove those from the map to just keep a Map of ones that have other anagrams from your dictionary...

Just had a phone interview with Amazon and this was the exact question they asked. Interesting problem if you have more than 10 minutes to solve it. — Javamann, Jun 14 '12 at 20:46

score 0 · Answer 2 · edited Feb 19 '23 at 16:50

0

public boolean isAnagram(String str1, String str2){

    if (str1.length() != str2.length())
        return false;
   
        char[] s1=str1.toCharArray();
        char[] s2=str2.toCharArray();

        Arrays.sort(s1);
        Arrays.sort(s2);

        for (int i = 0; i < s1.length; i++) {
            if(s1[i] !=s2[i]){
                return false;
            }
        }

        return true;
    }

edited Feb 19 '23 at 16:50

Adrian Mole

49,934
160
51
83

answered Feb 16 '23 at 02:57

justdizzle

9
1
4

1

A brief explanation will help others understand your answer. – SBMVNO Feb 21 '23 at 02:23

score 0 · Answer 3 · answered Feb 17 '12 at 01:29

0

You could use a Map that maps an ordered String to a Collection of array indices that are anagrams of the ordered String.

answered Feb 17 '12 at 01:29

João Silva

89,303
29
152
158

Java anagram finder algorithm

3 Answers3