[LeetCode] Anagrams (Java)

Given an array of strings, return all groups of strings that are anagrams.

Note: All inputs will be in lower-case.

Analysis

It would be easy to determine whether two strings are anagrams when we sort them. The complexity of sorting a string, which length is n, is $O(nlogn)$. Comparing two strings will cost $O(n)$. We can use a HashMap, in which we use the sorted string as the key, and a list as the value. In the list we will save all strings that have the same key, which is the sorted string. After we have processed all strings, we will check every list to see if the size of it is larger than 1. If it’s larger than 1, it means that there are several strings that are anagrams.

Code

public class Solution {
    public List<String> anagrams(String[] strs) {
        HashMap<String, LinkedList<String>> dict = new HashMap<>();
        for (int i = 0; i < strs.length; i++) {
            String s = strs[i];
            char[] chars = s.toCharArray();
            Arrays.sort(chars);
            String sortedString = String.valueOf(chars);
            if (dict.containsKey(sortedString)) {
                dict.get(sortedString).add(s);
            } else {
                LinkedList<String> list = new LinkedList<>();
                list.add(s);
                dict.put(sortedString, list);
            }
        }
        List<String> ret = new LinkedList<>();
        for (LinkedList<String> list : dict.values()) {
            if (list.size() > 1)
                ret.addAll(list);
        }
        return ret;
    }
}

public class Solution {

public List<String> anagrams(String[] strs) {

HashMap<String, LinkedList<String>> dict = new HashMap<>();

for (int i = 0; i < strs.length; i++) {

String s = strs[i];

char[] chars = s.toCharArray();

Arrays.sort(chars);

String sortedString = String.valueOf(chars);

if (dict.containsKey(sortedString)) {

dict.get(sortedString).add(s);

} else {

LinkedList<String> list = new LinkedList<>();

list.add(s);

dict.put(sortedString, list);

}

List<String> ret = new LinkedList<>();

for (LinkedList<String> list : dict.values()) {

if (list.size() > 1)

ret.addAll(list);

}

return ret;

}

Complexity

Assuming there are k strings, and the average length of string is n, the complexity will be $O(knlogn)$.