LeetCode49 字符异位词分组

题目

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

示例:
输入: ["eat", "tea", "tan", "ate", "nat", "bat"]
输出:
[
  ["ate","eat","tea"],
  ["nat","tan"],
  ["bat"]
]

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

方法

此题的解法都是将相同字母的数字存入同一数组（对于hashmap的一个kv），重点在于如何辨别顺序不同的字符串包含相同字符

排序法

将字符串的字符排序后判断，字符相同的字符串排序后均相同

• 时间复杂度：O(knlogn)，k为字符串的个数，nlogn是排序的时间
• 空间复杂度：O(kn)，k为字符串的个数，n为字符串的最大长度

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String,List<String>> map = new HashMap<>();
        for(String s:strs){
            char[] c = s.toCharArray();
            Arrays.sort(c);
            String key = String.valueOf(c);
            if(!map.containsKey(key)){
                map.put(key,new ArrayList<String>());
            }
            map.get(key).add(s);
        }
        return new ArrayList(map.values());

    }
}

字符数组法

由于总共26个字符，参考桶排序的思想，把字符放入对应的位置，相同字符的字符串在对应后的字符数组一致

• 时间复杂度：O()
• 空间复杂度：O()

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String,List<String>> map = new HashMap<>();
        for(String s:strs){
            char[] dic = new char[26];
            for(int i=0;i<s.length();i++){
                dic[s.charAt(i)-‘a‘]++;
            }
            String key = String.valueOf(dic);
            if(!map.containsKey(key)){
               map.put(key,new ArrayList<String>());
            }
            map.get(key).add(s);
        }
        return new ArrayList(map.values());
    }
}

LeetCode49 字符异位词分组

原文：https://www.cnblogs.com/ermiao-zy/p/14956428.html