1
\$\begingroup\$

Scan the array of strings, for each string get the code(which is nothing but the summation of char values of the string) and add the string to TreeSet<String> corresponding to the code if the code exists in the hashmap and if the string is an anagram with the first string in the TreeSet corresponding to the code else create a new TreeSet<String> and add the string to it and put it in the HashMap<Integer, TreeSet<String>>. Finally convert the all the sets in the HashMap to list of lists and return the same.

import java.util.Arrays;
import java.util.HashMap;
import java.util.ArrayList;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.TreeSet;

public class Anagrams {
    public static boolean anagramsHelper(String[] words) {
        for (int i = 1; i < words.length; i++) {
            if (!areAnagrams(words[0], words[i])) {
                return false;
            }
        }
        return true;
    }

    public static boolean areAnagrams(String word1, String word2) {
        if (word1.length() != word2.length()) {
            return false; // anagrams are strings with same length
        }
        int[] charCount = new int[128]; // 128 unique chars in ASCII
        // count the chars in word1
        for (int i = 0; i < word1.length(); i++) {
            charCount[(int) word1.charAt(i)]++;
        }
        // decrement the char count for chars in word2
        for (int i = 0; i < word2.length(); i++) {
            if (charCount[(int) word2.charAt(i)] == 0) {
                return false;
            }
            charCount[(int) word2.charAt(i)]--;
        }
        // verify if any char count is non zero
        // for anagrams it should be zero else they are not anagrams
        for (int i = 0; i < 128; i++) {
            if (charCount[i] != 0) {
                return false;
            }
        }
        return true;
    }

    public static List<List<String>> groupAnagrams(String[] words) {
        Map<String, TreeSet<String>> anagramsGroup = new HashMap<String, TreeSet<String>>();
        TreeSet<String> listOfAnagrams;
        String keyValue;
        for (String word : words) {
            char[] charsInWord = word.toCharArray();
            Arrays.sort(charsInWord);
            keyValue = String.valueOf(charsInWord);
            if (anagramsGroup.containsKey(keyValue)) {
                listOfAnagrams = anagramsGroup.get(keyValue);
                if (areAnagrams(word, listOfAnagrams.first())) {
                    listOfAnagrams.add(word);
                    anagramsGroup.put(keyValue, listOfAnagrams);
                }

            } else {
                listOfAnagrams = new TreeSet<>();
                listOfAnagrams.add(word);
                anagramsGroup.put(keyValue, listOfAnagrams);
            }

        }
        List<List<String>> groupsOfAnagrams = new ArrayList<List<String>>();
        for (Set<String> setOfAnagrams : anagramsGroup.values()) {
            List<String> anagramsList = new ArrayList<>(setOfAnagrams);
            groupsOfAnagrams.add(anagramsList);
        }
        return groupsOfAnagrams;
    }

    public static void main(String[] args) {
        String[] words = { "man", "elephand", "nam", "viswa", "v", "i",
                "handelep", "aba", "baa", "aab", "xyz", "yyy" };
        System.out.println(groupAnagrams(words));
    }
}
\$\endgroup\$
  • \$\begingroup\$ You might want to address one flaw -- if your test set includes "yyy" and "xyz" only one will show up in the results, because the ascii values add up to the same number. \$\endgroup\$ – Hank D Apr 18 '16 at 21:26
  • \$\begingroup\$ You might change your wordCode from an int to a String that contains the letters of a word sorted in alphabetical order. So, the word code for "man" and "nam" would be "amn". Then you wouldn't have the problem of "xyz" and "yyy" having the same word code. \$\endgroup\$ – Hank D Apr 18 '16 at 21:30
  • \$\begingroup\$ Nice catch. Fixed it :) \$\endgroup\$ – saneGuy Apr 19 '16 at 14:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.