【leetcode-49】字母异位词分组

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

示例:

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

所有输入均为小写字母。
不考虑答案输出的顺序。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/group-anagrams

这题没什么技巧，关键在于有没有想到用Map映射 ans : {String -> List}分类

排序数组分类

思路：当且仅当它们的排序字符串相等时，两个字符串是字母异位词。

我的代码：

public class Solutiontemp {

    public List<List<String>> groupAnagrams(String[] strs) {

        HashMap<String,ArrayList<String>> map = new HashMap<>();

        for (int i=0;i<strs.length;i++) {

            char[] c = strs[i].toCharArray();

            Arrays.sort(c);

            String key = String.valueOf(c);

//            String key = c.toString();  这个写法会输出错误，两个排列相同的char[]是不同的对象，toString后居然也是不同的对象

            if (map.containsKey(key)) {

                ArrayList<String> list = new ArrayList<>(map.get(key));

                list.add(strs[i]);

                map.put(key,list);

            } else {

                ArrayList<String> list = new ArrayList<>();

                list.add(strs[i]);

                map.put(key,list);

            }

        }

        List<List<String>> res = new ArrayList<>();

        for (String key : map.keySet()) {

            System.out.println(key);

            res.add(map.get(key));

        }

        return res;

    }

    public static void main(String[] args) {

        String[] str = new String[]{"eat","tea","tan","ate","nat","bat"};

        Solutiontemp solutiontemp

                 = new Solutiontemp();

        System.out.println(solutiontemp.groupAnagrams(str));

    }

}

同样思路参考解法很简洁：

class Solution {

    public List<List<String>> groupAnagrams(String[] strs) {

        if (strs == null || strs.length ==0)  return new ArrayList<List<String>>();

        Map<String, List<String>> map= new HashMap<>();

        for (String str : strs) {

            char[] tmp = str.toCharArray();

            Arrays.sort(tmp);

            String keyStr = String.valueOf(tmp);

            if (! map.containsKey(keyStr)) map.put(keyStr,new ArrayList<String>());

            map.get(keyStr).add(str);

        }

        return new ArrayList<>(map.values());

    }

}

链接：https://leetcode-cn.com/problems/two-sum/solution/zhao-dao-wei-yi-de-

巴特西

【leetcode-49】字母异位词分组

排序数组分类

最新文章

热门文章