leetcode49:字母异位词分组

给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。

字母异位词 是由重新排列源单词的所有字母得到的一个新单词。

示例 1:

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

示例 2:

输入: strs = [""]
输出: [[""]]

示例 3:

输入: strs = ["a"]
输出: [["a"]]

提示：

• 1 <= strs.length <= 104
• 0 <= strs[i].length <= 100
• strs[i] 仅包含小写字母

算法思路

1. 初始化一个哈希表 map，用于存储字母频率作为键，异位词列表作为值。
2. 遍历字符串数组 strs，对于每个字符串：
   • 创建一个长度为26的字符串 count，用于记录每个字母的出现次数。
   • 遍历字符串中的每个字符，计算其频率，并更新 count。
   • 将当前字符串添加到 map 中对应 count 的列表中。
3. 遍历哈希表 map，将每个键对应的异位词列表添加到结果数组 ans 中。

时间复杂度和空间复杂度

• 时间复杂度：O(N * M)，其中 N 是字符串数组的长度，M 是字符串的最大长度。每个字符串需要遍历来计算字母频率。
• 空间复杂度：O(N * M)，用于存储哈希表和结果数组。

启示

通过使用字母频率作为键来唯一标识异位词，我们可以高效地对字符串进行分组，而不需要对字符串进行排序。这种方法在处理大规模数据集时尤其有效，因为它减少了比较和排序的开销。

实际应用

• 文本分类：在自然语言处理中，可以通过分组异位词来帮助识别单词的相似性，从而进行文本分类或主题建模。
• 拼写检查：在拼写检查工具中，可以将用户输入的单词与预存的异位词组进行匹配，以提供更准确的拼写建议。

例如，在拼写检查工具中，如果用户输入了 “teh”，则算法可以识别出 “hte” 和 “the” 是其异位词，并将它们作为可能的正确拼写返回给用户。实现方法如下：

1. 使用上述算法将预存的单词列表分组为异位词组。
2. 当用户输入一个单词时，对其进行频率计算以找到其异位词键。
3. 在哈希表中查找该键，并返回相应的异位词组作为拼写建议。