字母异位词分组

给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。

示例:

输入: ["eat", "tea", "tan", "ate", "nat", "bat"]
输出:
[
  ["ate","eat","tea"],
  ["nat","tan"],
  ["bat"]
]
说明：

所有输入均为小写字母。
不考虑答案输出的顺序。
通过次数124,766提交次数194,667

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/group-anagrams
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

利用哈希表统计正确的词语，然后暴力比较

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        int[][] bucket = new int[strs.length][26];

        for (int i = 0; i < strs.length; i++) {
            String str = strs[i];
            for (int j = 0; j < str.length(); j++) {
                bucket[i][str.charAt(j) - 'a']++;
            }
        }
        List<List<String>> result = new ArrayList<>();
        for (int i = 0; i < strs.length; i++) {
            List<String> inner = new ArrayList<>();
            if (strs[i].equals("0")) {
                continue;
            }
            inner.add(strs[i]);
            for (int j = i + 1; j < strs.length; j++) {

                if (strs[j].equals("0")) {
                    continue;
                }
                boolean flag = true;

                for (int t = 0; t < 26; t++) {
                    if (bucket[i][t] != bucket[j][t]) {
                        flag = false;
                        break;
                    }
                }
                if (flag) {
                    inner.add(strs[j]);
                    strs[j] = "0";
                }

            }
            result.add(inner);
        }


        return result;
    }
}

对字符串排序，并使用字典对字符串分类，异位的字符串分到同一类别

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        if (strs.length == 0) return new ArrayList();
        Map<String, List> ans = new HashMap<String, List>();
        for (String s : strs) {
            char[] ca = s.toCharArray();
            Arrays.sort(ca);//首先对字母进行排序
            String key = String.valueOf(ca);//然后以排序后的字符作为字典的键值
            if (!ans.containsKey(key)) ans.put(key, new ArrayList());//将原来的字符串以链表的形式保存在map的值中
            ans.get(key).add(s);
        }
        return new ArrayList(ans.values());
    }
}

使用桶计数计算字符串的唯一识别串

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        if (strs.length == 0) return new ArrayList();
        Map<String, List> ans = new HashMap<String, List>();
        int[] count = new int[26];
        for (String s : strs) {
            Arrays.fill(count, 0);
            for (char c : s.toCharArray()) count[c - 'a']++;//先对字符串进行桶计数

            StringBuilder sb = new StringBuilder("");
            for (int i = 0; i < 26; i++) {//生成某个字符串的唯一识别字符串作为Map的key
                sb.append('#');//不加#号时，当用例为 ["bdddddddddd", "bbbbbbbbbbc"] ，生成的Map key值为[ 010100000000000000000000000 010100000000000000000000000] ，就通过不了哦！
                sb.append(count[i]);
            }
            String key = sb.toString();
            if (!ans.containsKey(key)) ans.put(key, new ArrayList());
            ans.get(key).add(s);
        }
        return new ArrayList(ans.values());
    }
}

参考文献

官方题解

作者：LeetCode
链接：https://leetcode-cn.com/problems/group-anagrams/solution/zi-mu-yi-wei-ci-fen-zu-by-leetcode/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

赏

谢谢你请我吃糖果

微信