Leetcode 题目解析之 Group Anagrams

原创

ruochen

发布于 2022-01-10 20:12:35

1.3K0

发布于 2022-01-10 20:12:35

文章被收录于专栏：若尘的技术专栏若尘的技术专栏

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:

For the return value, each inner list's elements must follow the lexicographic order.

All inputs will be in lower-case.

把每个string，按照字母分组，如”abc”和”cba”是一组
维护一个map，key是abc，value是abc一组string出现的下标
把每一组string找出，排序，加入结果

    public List<List<String>> groupAnagrams(String[] strs) {
        if (strs == null || strs.length == 0) {
            return new ArrayList<List<String>>();
        }
        List<List<String>> rt = new ArrayList<List<String>>();
        Map<String, ArrayList<Integer>> map = new HashMap<String, ArrayList<Integer>>();
        // 把单词分组
        for (int i = 0; i < strs.length; i++) {
            char[] c = strs[i].toCharArray();
            Arrays.sort(c);
            String k = Arrays.toString(c);
            ArrayList<Integer> list = new ArrayList<Integer>();
            if (map.containsKey(k)) {
                list = map.get(k);
            }
            list.add(i);
            map.put(k, list);
        }
        for (String s : map.keySet()) {
            List<Integer> l = map.get(s);
            List<String> group = new ArrayList<String>();
            // 把相同字母的单词放入同一个list
            for (Integer i : l) {
                group.add(strs[i]);
            }
            // 按字典序排序
            group.sort(new Comparator<String>() {
                public int compare(String x, String y) {
                    return x.compareTo(y);
                }
            });
            rt.add(group);
        }
        return rt;
    }

原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。

如有侵权，请联系 cloudcommunity@tencent.com 删除。

编程算法