Leetcode 49 - Group Anagrams

https://segmentfault.com/a/1190000003740929

Given an array of strings, group anagrams together.

For example, given: ["eat", "tea", "tan", "ate", "nat", "bat"],
Return:

[
  ["ate", "eat","tea"],
  ["nat","tan"],
  ["bat"]
]

Note:

1. For the return value, each inner list's elements must follow the lexicographic order.
2. All inputs will be in lower-case.

We can sort each string and store it in a hashmap to identify when a string has an anagram. The algorithm runs inO(n k log k). 

http://www.programcreek.com/2014/04/leetcode-anagrams-java/

public List<String> anagrams(String[] strs) { ArrayList<String> result = new ArrayList<String>(); if(strs == null || strs.length == 0) return result;   HashMap<String, ArrayList<Integer>> map = new HashMap<String, ArrayList<Integer>>(); for(int i=0; i<strs.length; i++){ char[] arr = strs[i].toCharArray(); Arrays.sort(arr); String t = String.valueOf(arr); if(map.get(t) == null){ ArrayList<Integer> l = new ArrayList<Integer>(); l.add(i); map.put(t, l); }else{ map.get(t).add(i); } }   for(ArrayList<Integer> l: map.values()){ if(l.size() > 1){ for(Integer i: l){ result.add(strs[i]); } } }   return result; }

https://leetcode.com/discuss/58561/share-my-short-java-solution
public List<List<String>> groupAnagrams(String[] strs) { if (strs == null || strs.length == 0) return new ArrayList<List<String>>(); Map<String, List<String>> map = new HashMap<String, List<String>>(); Arrays.sort(strs); for (String s : strs) { char[] ca = s.toCharArray(); Arrays.sort(ca); String keyStr = String.valueOf(ca); if (!map.containsKey(keyStr)) map.put(keyStr, new ArrayList<String>()); map.get(keyStr).add(s); } return new ArrayList<List<String>>(map.values());//\\ }

Code from http://www.darrensunny.me/leetcode-anagrams/
public ArrayList<String> anagrams(String[] strs) {
    ArrayList<String> res = new ArrayList<String>();
    if(strs == null || strs.length == 0)
        return res;
    HashMap<String, ArrayList<String>> map = new HashMap<String, ArrayList<String>>();
    for(int i=0;i<strs.length;i++)
    {
        char[] charArr = strs[i].toCharArray();
        Arrays.sort(charArr);
        String str = new String(charArr);
        if(map.containsKey(str))
        {
            map.get(str).add(strs[i]);
        }
        else
        {
            ArrayList<String> list = new ArrayList<String>();
            list.add(strs[i]);
            map.put(str,list);
        }
    }
    Iterator iter = map.values().iterator();
    while(iter.hasNext())
    {
        ArrayList<String> item = (ArrayList<String>)iter.next();
        if(item.size()>1)
            res.addAll(item);
    }
    return res;
}
https://segmentfault.com/a/1190000003740929

    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> map = new HashMap<String, List<String>>();
        for(String str : strs){
            // 将单词按字母排序
            char[] carr = str.toCharArray();
            Arrays.sort(carr);
            String key = new String(carr);
            List<String> list = map.get(key);
            if(list == null){
                list = new ArrayList<String>();
            }
            list.add(str);
            map.put(key, list);
        }
        List<List<String>> res = new ArrayList<List<String>>();
        // 将列表按单词排序
        for(String key : map.keySet()){
            List<String> curr = map.get(key);
            Collections.sort(curr);
            res.add(curr);
        }
        return res;
    }

http://www.tangjikai.com/algorithms/leetcode-49-anagrams

1. def groupAnagrams(self, strs):
2. ans = []
3. dic = collections.defaultdict(list)
5. for s in strs:
6. dic[str(sorted(s))].append(s)
8. for value in dic.values():
9. ans.append(sorted(value))
11. return ans

https://discuss.leetcode.com/topic/99/group-numbers-via-digits-frequency/

A list of numbers are given. We need to find the total number of groups in which the digits of each number have same frequency.
For example if numbers are:
1
10
303
330

There are 3 groups:
G1={1}has one 1.
G2={10} has one 1 and one 0.
G3={330, 303} has one 0 and two 3s

A variation of Group Anagrams?

Just sort the digits of each number and de-dupe them

class AnagramComparator implements Comparator<String> {
public String sortChars(String s) {
        char[] content= s.toCharArray();
        Arrays.sort(content);
        return new String(content);
}

public int compare(String sl, String s2) {
        return sortChars(sl).compareTo(sortChars(s2));
}
}
Arrays.sort(array, new AnagramComparator());
This algorithm will take O(n log(n)) time.

void sort(String[] array) {
        HashMaplist<String, String> maplist = new HashMaplist<String, String>();

        /* Group words by anagram */
        for (String s : array) {
                String key= sortChars(s);
                maplist.put(key, s);
        }
        // Convert hash table to array*
        int index = 0;
        for (String key: maplist.keySet()) {
                Arraylist<String> list= maplist.get(key);
                for (String t : list) {
                        array[index] = t;
                        index++;
                }
        }
}
/*HashMapList<String, Integer> is a HashMap that maps from Strings to
 * Arraylist<Integer>. See appendix for implementation. */
Read full article from My Own Notes: Leetcode: Anagrams