面试题 10.02. 变位词组

解法一

采用Map存储变位词数组，关键在于如何对单词字符串进行编码，求得其加入Map时对应的Key值，使得变位单词具有相同的Key值且能够区分非变位单词。
两种主流的编码的方式如下

• 对单词中的字符进行排序
• 统计各个字符的出现次数，按照次数进行编码（题中限定仅出现小写字母）
• （补充）取前26个质数相乘编码

考虑到单词长度一般不会很长，第一种编码方式的表现会更佳。

import java.util.*;
class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> map = new HashMap<>();
        for (String str : strs) {
            String key = getKey_1(str);
            if (map.containsKey(key)) {
                map.get(key).add(str);
            } else {
                LinkedList list = new LinkedList<>();
                list.add(str);
                map.put(key, list);
            }
        }
        return new ArrayList<List<String>>(map.values());
    }
    public String getKey_1(String str) {
        char[] chars = str.toCharArray();
        Arrays.sort(chars);
        return new String(chars);
    }
    public String getKey_2(String str) {
        int[] count = new int[26];
        char[] chars = str.toCharArray();
        for (char i : chars) {
            ++count[i - 97];
        }
        StringBuilder stringBuilder = new StringBuilder(100);
        for (int i = 0; i < count.length; ++i) {
            stringBuilder.append(count[i] + "|");
        }
        return stringBuilder.toString();
    }
}