字母异位词分组
Group Anagrams
题目详情
问题：字母异位词分组
考察：数组、字符串
来源：Citadel
链接：https://www.jointaro.com/interviews/questions/group-anagrams/
Given an array of strings strs, group the anagrams together. You can return the answer in any order.
Example 1:
Input: strs = ["eat","tea","tan","ate","nat","bat"]
Output: [["bat"],["nat","tan"],["ate","eat","tea"]]
Explanation:
- There is no string in strs that can be rearranged to form
"bat". - The strings
"nat"and"tan"are anagrams as they can be rearranged to form each other. - The strings
"ate","eat", and"tea"are anagrams as they can be rearranged to form each other.
Example 2:
Input: strs = [""]
Output: [[""]]
Example 3:
Input: strs = ["a"]
Output: [["a"]]
Constraints:
1 <= strs.length <= 1040 <= strs[i].length <= 100strs[i]consists of lowercase English letters.
解析
思路：字母异位词有相同的字符计数。对每个单词生成签名：可以排序字符串，也可以统计 26 个字母频次，然后用哈希表把签名相同的单词分组。
复杂度：排序签名 O(totalLen log L)，计数签名 O(totalLen)，空间 O(totalLen)。