3
\$\begingroup\$

I have written code to return anagrams from a list of words. I'm a newbie in time complexity analysis so pardon my ignorance if this is a blatantly obvious question. Am I right in thinking this is in O(n log n) time, since it's just performing a quicksort and the rest is done in O(1) time because it's hashmaps? Also any suggestions on improving the code?

    public class anagram {

public static ArrayList<String> anagrams(String[] original) {


    HashMap<String, ArrayList<String>> map = new HashMap();


    for(String str : original) {

        String key = sortChars(str);

        if(!map.containsKey(key)) {
            map.put(key, new ArrayList<String>());
        }

        ArrayList<String> anagramList = map.get(key);
        anagramList.add(str);
    }

    ArrayList<String> result = new ArrayList();

    for(String key : map.keySet()) {

        ArrayList<String> anagramList = map.get(key);

        if(anagramList.size() > 1) {

            result.addAll(anagramList);            
        }
    }

    return result;
}
\$\endgroup\$
3
\$\begingroup\$

You are close to right on the complexity. You have two dimensions that are independent in your system though. The sort is sorting the letters in a word, and its performance is dependent on the length of the word, not the number of words.

You have essentially an outer loop which is linear \$O(n)\$ and an inner sort which is dependent on m, the number of letters in each word...., and those combine to create an overall complexity of \$O({n} \times {m}\log{m})\$

If you double the average size of each word, the execution time will slightly-more-than-double. If you double the number of words, the same will happen.

Now, how can it be improved?

  • your class is called anagram ? It should be capitalized to Anagram.
  • you should use the interface declaration not the implementation, where you can. For example, your HashMap should be HashMap<String, List<String>> instead of HashMap<String, ArrayList<String>> (note, use List instead of ArrayList).
  • The two lines:

    ArrayList<String> anagramList = map.get(key);
    anagramList.add(str);
    

    could be simplified to:

    map.get(key).add(str);
    
  • You iterate through the keys of the HashMap to get the value arrays, but you don't need to. Consider the following (which just iterates the values...):

    for (List<String> anagramList : map.values()) {
        if (anagramList.size() > 1) {
            result.addAll(anagramList);
        }
    }
    
\$\endgroup\$
  • \$\begingroup\$ Thanks so much for clarifying that for me. You've been really helpful :) \$\endgroup\$ – B.oof Sep 23 '14 at 1:51

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.