8
\$\begingroup\$

Question:

An anagram is a word that can be written as a permutation of the characters of another word, like "dirty room" and "dormitory"(ignore spaces). However, "the" and "thee" are not anagrams, since "the" only has a single "e" whereas "thee" has two "e" characters (spaces can occur zero, or multiple times, however).

Give a list of words as input, you should output another list of strings, each containing words that are mutual anagrams.

Each string of the output should be a single group of anagrams joined with commas.

Within an output string, the expressions should be sorted lexicographically. If a group contains only a single element, output that one-element group as a single string. And the strings should also be output in lexicographical order.

Given e.g.:

  • pear
  • amleth
  • dormitory
  • tinsel
  • dirty room
  • hamlet
  • listen
  • silent

The output would be:

amleth,hamlet
dirty room,dormitory
listen,silent,tinsel
pear

My solution is:

  1. Convert into each string to a char array, and in the meantime, compare to each char array group. After that, get how many groups for an input string array, and divide them into a respective group.
  2. Sort each group alphabetically, and eventually order by group.

Time-complexity is \$O(n^2)\$

I wrote code for this question, and it has a poor time-complexity. Are there any suggestions for this?

ArrayList<char[]> group = new ArrayList<char[]>();
    ArrayList<ArrayList<String>> originalList = new ArrayList<ArrayList<String>>();
    String[] tempstr = str.clone(); //clone could do deep copy, and avoid to change str.

    //Category group for str.
    outerloop:
    for(int pos=0; pos<tempstr.length; pos++){
        tempstr[pos]= tempstr[pos].trim().replaceAll(" ", "");
        char[] c = new char[tempstr[pos].length()];
        tempstr[pos].getChars(0,tempstr[pos].length(),c,0); //last character is at index srcEnd-1 
        Arrays.sort(c);//ignore character's order in string.
        ArrayList<String> sArrList = new ArrayList<String>();

        Iterator<char[]> it = group.iterator();
        while(it.hasNext()){
            sArrList.clear();
            char[] comparedChars = (char[])it.next();
            if(Arrays.equals(comparedChars,c)){//only compare character in same index.
                sArrList = originalList.get(group.indexOf(comparedChars));
                sArrList.add(str[pos]);
                continue outerloop;
            }
        }
        // can not find group
        sArrList.add(str[pos]);
        originalList.add(sArrList);
        group.add(c);
    }

    //Following begin to do sorting.
    String[] groupStr = new String[group.size()];
    Iterator<ArrayList<String>> it2 = originalList.iterator();
    for(int groupId=0 ; groupId<group.size() && it2.hasNext(); groupId++){
        ArrayList<String> temp = it2.next();
        Collections.sort(temp); // let string in each single row sort by alphabet.
        for(Iterator it3 = temp.iterator();it3.hasNext();){
            String ss = (String) it3.next();
            if(groupStr[groupId]==null || groupStr[groupId].length()==0) groupStr[groupId] = ss;
            else groupStr[groupId] += "," + ss;
        }
    }
\$\endgroup\$
0
7
\$\begingroup\$

A different way would be to use primeHashes (see https://stackoverflow.com/a/4237875/461499).

This prevents the need to sort.

private static void printAnagrams2(List<String> input) {

    // our result structure.
    // key in the map is the sorted list of characters of the string
    // value is the list of anagrams found for this key
    Map<BigInteger, List<String>> result = new HashMap<BigInteger, List<String>>();

    for (String s : input) {
        BigInteger primeHash = calcPrimeHash(s);

        // Then add-or-create this in the resultmap
        if (result.containsKey(primeHash)) {
            result.get(primeHash).add(s);
        } else {
            List anagrams = new ArrayList<String>();
            anagrams.add(s);
            result.put(primeHash, anagrams);
        }
    }

    // sort each anagram-list
    result.values().forEach(Collections::sort);

    // and print
    result.values().forEach(System.out::println);
}

private static int[] primes = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101};

private static BigInteger calcPrimeHash(String s) {
    BigInteger i = BigInteger.valueOf(1);
    for (char ch : s.toCharArray())
    {
        if (Character.isLetter(ch))
        {
            char c = Character.toLowerCase(ch);
            i = i.multiply(BigInteger.valueOf(primes[c - 'a']));
        }
    }
    return i;
}
\$\endgroup\$
4
  • \$\begingroup\$ Nice solution, it seems this one is better the List<Char> key \$\endgroup\$ Jul 23 at 8:56
  • \$\begingroup\$ We need to sort result as well, "amleth" should be on the top \$\endgroup\$ Jul 23 at 10:59
  • 1
    \$\begingroup\$ That is an exercise to the reader ;) \$\endgroup\$ Jul 28 at 14:54
  • \$\begingroup\$ I finished the exercise. Please review :D codereview.stackexchange.com/a/264344/245276 \$\endgroup\$ Jul 29 at 1:56
5
\$\begingroup\$

[Work in progress]

Nice question. I assume you come from a C background? That it what your code looks like.

My main feedback would be to use Java's own classes and methods instead of implementing your own.

Don't do too much String operations

Your code does a trim() and a replaceAll(), in effect iterating the String twice, before you even do something useful with it. Also, you only check for whitespace. A safer way would be to filter the characters you need.

Naming

You have a lot of variables, some with the type in their name. Too many variables (with long, difficult names) make your code confusing. Give then names that denote their function not their type

Control structures and escape labels

While they might be useful, it is almost always a sign of something that coul be implemented simpler. Java provides you with very nice enhanced for loops, which make code easier to read. Easier to read code makes it easier to see optimisations as well.

My solution is:

private static void printAnagrams(List<String> input) {

    //our result structure.
    //key in the map is the sorted list of characters of the string
    //value is the list of anagrams found for this key
    Map<List<Character>, List<String>> result  = new HashMap<List<Character>, List<String>>();

    for (String s : input)
    {

        //First, create a sortedString
        List<Character> allLetters = new ArrayList<Character>();
        for (char ch : s.toCharArray())
        {
            if (Character.isLetter(ch))
            {
                allLetters.add(ch);
            }
        }
        Collections.sort(allLetters);



        //Then add-or-create this in the resultmap
        if (result.containsKey(allLetters))
        {
            result.get(allLetters).add(s);
        }
        else
        {
            List anagrams = new ArrayList<String>();
            anagrams.add(s);
            result.put(allLetters, anagrams);
        }
    }

    //sort each anagram-list
    result.values().forEach(Collections::sort)  ;

    //and print
    result.values().forEach(System.out::println);
}
\$\endgroup\$
2
  • 1
    \$\begingroup\$ If I understand correctly your code could not handle duplicate letters, i.e. hamlet, hamlett, hamlettt and so on since sets guarantee freedom from duplicates (of letters in this case). \$\endgroup\$
    – vonludi
    Jan 20 '17 at 7:45
  • 1
    \$\begingroup\$ Ah yey, you are correct :) I need more coffee and switch to a Bag implementation. Fixed. \$\endgroup\$ Jan 20 '17 at 7:46
0
\$\begingroup\$

Thanks @RobAu to provide solutions, but there is a requirement that the head words should be sorted as well.

We need a custom class for TreeMap

class PrimeKey implements Comparable<PrimeKey> {
    BigInteger primeHash;
    String keyword;
    PrimeKey(BigInteger primeHash, String keyword) {
        this.primeHash = primeHash;
        this.keyword = keyword;
    }

    @Override
    public int compareTo(PrimeKey primeKey) {
        return this.keyword.compareTo(primeKey.keyword);
    }
}

Then reuse PrimeHash solution with additional steps that adding result into TreeMap for sorting

    private static void printAnagrams(List<String> input) {

        // our result structure.
        // key in the map is the sorted list of characters of the string
        // value is the list of anagrams found for this key
        Map<BigInteger, List<String>> result = new HashMap<>();

        for (String s : input) {
            BigInteger primeHash = calcPrimeHash(s);

            // Then add-or-create this in the resultmap
            if (result.containsKey(primeHash)) {
                result.get(primeHash).add(s);
            } else {
                List anagrams = new ArrayList<String>();
                anagrams.add(s);
                result.put(primeHash, anagrams);
            }
        }

        // sort each anagram-list
        result.values().forEach(Collections::sort);
        Map<PrimeKey, List<String>> sortedResult = new TreeMap<>();

        for (BigInteger key : result.keySet()) {
            List<String> strings = result.get(key);
            sortedResult.put(new PrimeKey(key, strings.get(0)), strings);
        }

        // and print
        sortedResult.values().forEach(System.out::println);
    }

    private static int[] primes = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101};

    private static BigInteger calcPrimeHash(String s) {
        BigInteger i = BigInteger.valueOf(1);
        for (char ch : s.toCharArray()) {
            if (Character.isLetter(ch)) {
                char c = Character.toLowerCase(ch);
                i = i.multiply(BigInteger.valueOf(primes[c - 'a']));
            }
        }
        return i;
    }
\$\endgroup\$
1
  • \$\begingroup\$ The main problem with your answer is that you are reviewing another answer rather than the original code. The best answer here is the one with more text and less code \$\endgroup\$
    – pacmaninbw
    Jul 24 at 13:34

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.