LeetCode 49. Group Anagrams（分組同構異形詞）

原題網址：https://leetcode.com/problems/anagrams/

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.

方法：用histogram作為key，尋找同構詞。

public class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        List<List<String>> results = new ArrayList<>();
        final char[][] sas = new char[strs.length][];
        for(int i=0; i<strs.length; i++) sas[i] = strs[i].toCharArray();
        List<Integer>[] keys = new List[strs.length];
        for(int i=0; i<sas.length; i++) {
            int[] f = new int[26];
            for(int j=0; j<sas[i].length; j++) f[sas[i][j]-'a'] ++;
            keys[i] = new ArrayList<>(26);
            for(int k=0; k<26; k++) keys[i].add(f[k]);
        }
        Map<List<Integer>, List<String>> groups = new HashMap<>();
        for(int i=0; i<strs.length; i++) {
            List<String> anagrams = groups.get(keys[i]);
            if (anagrams == null) {
                anagrams = new ArrayList<>();
                groups.put(keys[i], anagrams);
            }
            anagrams.add(strs[i]);
        }
        for(List<String> anagrams: groups.values()) {
            Collections.sort(anagrams);
            results.add(anagrams);
        }
        return results;
    }
}
           

另一種實作：

public class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<List<Integer>, List<String>> groups = new HashMap<>();
        for(String s: strs) {
            char[] sa = s.toCharArray();
            Integer[] h = new Integer[26];
            Arrays.fill(h, 0);
            for(char c: sa) h[c-'a'] ++;
            List<Integer> key = Arrays.asList(h);
            List<String> group = groups.get(key);
            if (group == null) {
                group = new ArrayList<>();
                groups.put(key, group);
            }
            group.add(s);
        }
        List<List<String>> results = new ArrayList<>();
        results.addAll(groups.values());
        return results;
    }
}