0049. Group Anagrams - kumaeki/LeetCode GitHub Wiki

0049. Group Anagrams

Given an array of strings strs, group the anagrams together. You can return the answer in any order.

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

Example 1:

Input: strs = ["eat","tea","tan","ate","nat","bat"]

Output: [["bat"],["nat","tan"],["ate","eat","tea"]]

Example 2:

Input: strs = [""]

Output: [[""]]

Example 3:

Input: strs = ["a"]

Output: [["a"]]

Constraints:

  • 1 <= strs.length <= 10^4
  • 0 <= strs[i].length <= 100
  • strs[i] consists of lower-case English letters.

解法1

把每个字符串中出现的字符的个数统计一下, 然后找到相同的编到一组中.

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> map = new HashMap<>();
        for(String s : strs){
            String key = getKey(s);
            if(!map.containsKey(key))
                map.put(key, new ArrayList<String>());
            
            map.get(key).add(s);
        }
        
        return new ArrayList<List<String>>(map.values());
    }
    
    // 得到对应的key
    // 字符串最大100, 所以每个位置3位就够用
    private String getKey(String s){
        int[] arr = new int[26];
        for(char c : s.toCharArray())
            arr[c - 'a']++;
        
        StringBuilder sb = new StringBuilder();
        for(int i : arr){
            String temp = String.valueOf(i);
            if(temp.length() == 1)
                sb.append("00").append(temp);
            else if(temp.length() == 2)
                sb.append("0").append(temp);
            else
                sb.append(temp);
        }
        
        return sb.toString();
    }
}

解法2

不强行补到3位, 而是用其他符号(#)隔开也可以

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List> ans = new HashMap<String, List>();
        for (String s : strs) {
            int[] count = new int[26];
            for (char c : s.toCharArray()) 
                count[c - 'a']++;

            StringBuilder sb = new StringBuilder("");
            for (int i = 0; i < 26; i++) {
                sb.append('#');
                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());
    }
}
⚠️ **GitHub.com Fallback** ⚠️