LeetCode无排序字母异位词分组方案的两大技术疑问

问题1：为什么将int数组转为字符串作为HashMap的键？ #

字母异位词的核心特征是每个字符的出现次数完全相同，所以它们对应的长度为26的int计数数组（每个位置对应a-z的出现次数）内容完全一致。

但Java里的数组不能直接作为HashMap的键——因为数组的equals()方法是比较对象引用，而非内容。也就是说，即使两个数组内容一模一样，它们在HashMap里会被判定为不同的键，无法实现分组。

而Arrays.toString(input)会把数组转成一个内容唯一的字符串：只要两个计数数组内容相同，转出来的字符串就完全一样；内容不同的数组，转出来的字符串也不同。这样一来，HashMap就能通过这个字符串键，把所有字符计数相同的异位词分到同一个List里，实现正确分组。

比如"eat"和"tea"的计数数组都是[1,0,0,0,1,0,...0,1,0,...]，转成字符串后完全相同，就会被映射到同一个List中。

问题2：该方案的时间复杂度是多少？ #

是的，该方案的时间复杂度为O(m*n)，其中：

• m是输入字符串数组的元素总数
• n是单个字符串的平均长度

复杂度分析： #

1. 外层循环遍历m个字符串，每个字符串执行以下操作：
   • 内层循环遍历字符串的n个字符，统计每个字符的出现次数，这部分是O(n)
   • Arrays.toString(input)将长度固定为26的数组转成字符串，这是O(1)的常数时间（因为数组长度固定，不管输入字符串多长，数组都是26位）
   • HashMap的containsKey()、get()、put()操作在平均情况下都是O(1)
2. 最后将HashMap的values集合转成输出List，是O(m)的时间，不影响整体复杂度

因此总时间复杂度是O(m*n)，这是字母异位词分组问题的最优时间复杂度之一。

附解决方案代码 #

public List<List<String>> groupAnagrams(String[] strs) {
    List<List<String>> output = new ArrayList();
    if(strs == null) {
        return output;
    }
    Map<String,List<String>> outputMap = new HashMap();

    for(String str : strs) {
        int[] input = new int[26];
        for(int i = 0; i < str.length(); i++) {
            input[str.charAt(i) - 'a']++;
        }
        String inputStr = Arrays.toString(input);
        if(outputMap.containsKey(inputStr)) {
            outputMap.get(inputStr).add(str);
        } else {
            List<String> outputLst = new ArrayList();
            outputLst.add(str);
            outputMap.put(inputStr, outputLst);
        }
    }
    output.addAll(outputMap.values());
    return output;
}

内容的提问来源于stack exchange，提问作者rickygrimes