LeetCode49- 字母异位词分组(Group Anagrams)

本文主要是介绍LeetCode49- 字母异位词分组(Group Anagrams)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

LeetCode49- 字母异位词分组(Group Anagrams)

最近全国疫情严重，待在家里没事干，马上又要准备春招了，最近刷刷题，记录一下！再说一句，武汉加油，大家出门记得戴口罩！

1、题目

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

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

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

2、思路

(哈希表)
定义从string 映射到 vector的哈希表：unordered_map<string, vector>，哈希表用法参见这里。
我们将每个字符串的所有字符从小到大排序，将排好序的字符串作为key，然后将原字符串插入key对应的vector中。
时间复杂度分析：N
是字符串个数，L 是字符串平均长度。对于每个字符串，哈希表和vector的插入操作复杂度都是 O(1)，排序复杂度是 O(LlogL)。所以总时间复杂度是 O(NLlogL)。

3、代码

class Solution {
public:vector<vector<string>> groupAnagrams(vector<string>& strs) {unordered_map<string, vector<string>> dict;for(auto str:strs){string key=str;sort(key.begin(),key.end());dict[key].push_back(str);}vector<vector<string>> res;for(auto i=dict.begin();i!=dict.end();i++){res.push_back(i->second);}return res;   }
};

Java

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