LeetCode——Group Anagrams

本文主要是介绍LeetCode——Group Anagrams，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Given an array of strings, group anagrams together.

• Example:
  Input: [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”],
  Output:
  [
  [“ate”,“eat”,“tea”],
  [“nat”,“tan”],
  [“bat”]
  ]

Note:

• All inputs will be in lowercase.
• The order of your output does not matter.

解法一

把每个字符串按字母大小排序，使用map来保存排序后的字符串与一组异位词的映射，遍历完数组后将map中每个key的异位词组加入res即可

public List<List<String>> groupAnagrams(String[] strs) {List<String> list=new ArrayList<String>();HashMap<String,List<String>> map=new HashMap<String,List<String>>();for(int i=0;i<strs.length;i++){char[] c=strs[i].toCharArray();Arrays.sort(c);String t=String.valueOf(c);if(!map.containsKey(t))map.put(t, new ArrayList<String>());map.get(t).add(strs[i]);}return new ArrayList(map.values());}

Runtime: 11 ms, faster than 99.11% of Java online submissions for Group Anagrams.
Memory Usage: 41.8 MB, less than 86.15% of Java online submissions for Group Anagrams.

解法二

将字母与0~25对应起来，用一个数组存储每个字符串内每个字母的数量，然后把数组转化为一个字符串作为map里的key

public List<List<String>> groupAnagrams(String[] strs){List<List<String>> res=new ArrayList<List<String>>();if(strs==null)return res;Map<String,List> map=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++)sb.append(count[i]);if(!map.containsKey(sb.toString()))map.put(sb.toString(), new ArrayList());map.get(sb.toString()).add(s);}return new ArrayList(map.values());}

Runtime: 22 ms, faster than 34.15% of Java online submissions for Group Anagrams.
Memory Usage: 43.3 MB, less than 50.87% of Java online submissions for Group Anagrams.

这篇关于LeetCode——Group Anagrams的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---