Leetcode - Group Anagrams

My code:

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;

public class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        if (strs == null)
            return null;
        ArrayList<List<String>> result = new ArrayList<List<String>>();
        ArrayList<String> group = new ArrayList<String>();
        if (strs.length == 0) {
            return result;
        }
        Arrays.sort(strs);
        HashMap<String, ArrayList<Integer>> hm = new HashMap<String, ArrayList<Integer>>();
        
        for (int i = 0; i < strs.length; i++) {
            char[] tempCharArray = strs[i].toCharArray();
            Arrays.sort(tempCharArray);
            String tempStr = String.valueOf(tempCharArray);
            if (!hm.containsKey(tempStr)) {
                ArrayList<Integer> tempArrayList = new ArrayList<Integer>();
                tempArrayList.add(i);
                hm.put(tempStr, tempArrayList);
            }
            else {
                ArrayList<Integer> tempArrayList = hm.get(tempStr);
                tempArrayList.add(i);
                hm.put(tempStr, tempArrayList);
            }
        }
        
        for (ArrayList<Integer> temp : hm.values()) {
            for (Integer index : temp)
                group.add(strs[index]);
            result.add(new ArrayList<String>(group));
            group = new ArrayList<String>();
        }
        return result;
    }
    
    public static void main(String[] args) {
        Solution test = new Solution();
        String[] a = {"a"};
        System.out.println(test.groupAnagrams(a));
    }
}

My test result:

Paste_Image.png

首先说下测试结果为什么这么慢。我的理解是，这道题目是8.9才改题的，之前的用户数据可能还保存着，导致我的排名很低。但其实，题目改了之后，复杂度就变了。
这道题目感觉学到了很多。

1. 如何对 string 排序， 利用java API

char[] arr = str.toCharArray();
Arrays.sort(arr);
String s = String.valueOf(arr);

2. 用什么去接收Collections 类。 如何获得 HashMap values 的迭代器,使用 .values() 方法
   如果value是 T 类型。那么，

for (T temp : hashmap.values())
  ......

3. new ArrayList<Integer>(5); 并不能生成一个 含有 5 的链表。必须要先new一个新的arraylist，然后再插入5进去。

**
总结： String, HashMap, Collections, string sort
**

Anyway, Good luck, Richardo!

My code:

public class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        ArrayList<List<String>> ret = new ArrayList<List<String>>();
        if (strs == null || strs.length == 0)
            return ret;
        /** key: sorted string  value: list for string, convenient for sorting later */
        HashMap<String, ArrayList<String>> tracker = new HashMap<String, ArrayList<String>>();
        for (int i = 0; i < strs.length; i++) {
            String curr = strs[i];
            char[] currChar = curr.toCharArray();
            Arrays.sort(currChar);
            curr = new String(currChar);
            if (tracker.containsKey(curr)) {
                List<String> list = tracker.get(curr);
                list.add(strs[i]);
            }
            else {
                ArrayList<String> list = new ArrayList<String>();
                list.add(strs[i]);
                tracker.put(curr, list);
            }
        }
        /** traverse the key set of hashmap, sort sub list and add into ret */
        for (String key : tracker.keySet()) {
            ArrayList<String> list = tracker.get(key);
            Collections.sort(list);
            ret.add(list);
        }
        return ret;
    }
}

这道题木卡了一会儿。问题出在哪里？
char[] tmp = ...
tmp.toString() 返回的是该数组的内存地址，而不是转换而来的 String!!
一定要当心。
其他没什么问题了。
对数组排序，
Arrays.sort();
对链表排序，
Collections.sort();

Anyway, Good luck, Richardo!

My code:

public class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        List<List<String>> ret = new ArrayList<List<String>>();
        HashMap<String, List<String>> map = new HashMap<String, List<String>>();
        for (int i = 0; i < strs.length; i++) {
            char[] arr = strs[i].toCharArray();
            Arrays.sort(arr);
            String s = String.valueOf(arr);
            if (map.containsKey(s)) {
                map.get(s).add(strs[i]);
            }
            else {
                map.put(s, new ArrayList<String>());
                map.get(s).add(strs[i]);
            }
        }
        
        for (String ss : map.keySet()) {
            Collections.sort(map.get(ss));
        }
        
        for (String ss : map.keySet()) {
            ret.add(map.get(ss));
        }
        return ret;
    }
}

并不难，但复杂度不小，因为每个string都需要sort

后来看到了一个新的方法，更高效，利用hashcode 的思想。
统计每个字母的个数与 int[26] nums
然后Arrays.hashCode(nums) 拿到哈希值作为hashtable的key

My code:

public class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        List<List<String>> ret = new ArrayList<List<String>>();
        if (strs == null || strs.length == 0) {
            return ret;
        }
        HashMap<Integer, List<String>> map = new HashMap<Integer, List<String>>();
        for (int i = 0; i < strs.length; i++) {
            int id = getID(strs[i]);
            if (!map.containsKey(id)) {
                map.put(id, new ArrayList<String>());
            }
            map.get(id).add(strs[i]);
        }
        
        for (Integer i : map.keySet()) {
            ret.add(map.get(i));
        }
        return ret;
    }
    
    private int getID(String s) {
        int[] nums = new int[26];
        for (int i = 0; i < s.length(); i++) {
            nums[s.charAt(i) - 'a']++;
        }
        return Arrays.hashCode(nums);
    }
}

reference:
https://discuss.leetcode.com/topic/56803/beat-90-2-18ms-o-n-non-sort-solutions-with-hashmap

Anyway, Good luck, Richardo! -- 09/20/2016