C++ 程序对给定字符串流中的同位词进行分组

变位词 (anagram) 是通过重新排列另一个词的字母而形成的词，例如 “listen” 和 “silent”。要在每个字符串流中对变位词进行分组，我们需要将所有互为变位词的字符串组合在一起。

示例 1

一个使用哈希表对变位词进行分组的 C++ 代码片段

输出

bat tan nat eat tea ate

在此实现中，我们首先创建一个无序映射 hashTable，其中键是排序后的字符串，值是互为变位词的字符串向量。之后，我们遍历输入向量 strs 中的每个字符串，对字符串进行排序以形成一个键，并将其添加到哈希表中。最后，我们清空输入向量 "strs"，并遍历哈希表，将变位词组附加到 strs 中。

在 C++ 中，还有其他方法可以对字符串流中的变位词进行分组。一种方法是使用一个由 pair 组成的向量，将排序后的字符串作为 pair 的第一个元素，原始字符串作为 pair 的第二个元素。之后，我们可以根据排序后的字符串对此 pair 向量进行排序，这样变位词就会彼此相邻。最后，我们可以提取原始字符串并将它们存储在一个单独的向量中。

示例 2

这是该方法的实现

输出

bat ate eat tea nat tan

在此实现中，我们首先创建一个由 pair 组成的向量 sortedStrs，其中每个 pair 的第一个元素是排序后的字符串，第二个元素是原始字符串。之后，我们遍历输入向量 strs 中的每个字符串，对字符串进行排序以形成排序后的字符串，并将该 pair 添加到 sortedStrs 中。我们使用 std::sort() 根据排序后的字符串对 sortedStrs 进行排序，该函数会根据 pair 的第一个元素按字典序对它们进行排序。最后，我们清空输入向量 "strs"，并遍历 sortedStrs 来提取每个 pair 的第二个元素并将其附加到 "strs" 中。

该方法的时间复杂度为 O(N * M * log M)，其中 N 是输入向量中的字符串数量，M 是最长字符串的长度。空间复杂度为 O(N * M)，因为我们需要为每个输入字符串存储排序后的字符串。

示例 3

另一种实现方式是使用计数排序方法

输出

bat tan nat eat tea ate

在此实现中，我们首先创建一个无序映射 map，其中键是根据字符串中每个字符的计数排序后的字符串，值是具有相同排序后字符串的原始字符串向量。之后，我们遍历输入向量 strs 中的每个字符串，使用一个计数数组 count 统计每个字符的频率，并通过将每个字符的计数与 "#" 分隔符连接来构造键。我们将原始字符串插入到 map 中对应键的值向量中。最后，我们清空输入向量 strs，并遍历 map 来提取值向量并将其元素附加到 strs 中。

还有其他几种方法，例如

• Trie（字典树）方法： 我们可以使用 Trie 数据结构根据排序后的字符串对变位词进行分组。我们可以将每个字符串先排序再插入到 Trie 中，并将原始字符串存储在其排序后字符串对应的叶子节点上。之后，我们可以遍历 Trie 来提取变位词组。该方法的时间复杂度为 O(N * M * log M)，其中 N 是输入向量中的字符串数量，M 是最长字符串的长度。
• 桶排序方法： 我们可以使用桶排序算法根据排序后的字符串对变位词进行分组。我们可以创建一个向量数组，其中每个向量的索引对应于排序后的字符串，并将原始字符串附加到该索引处的向量中。之后，我们可以连接数组中的向量来提取变位词组。该方法的时间复杂度为 O(N * M)，其中 N 是输入向量中的字符串数量，M 是最长字符串的长度。

所有这些方法都有各自的优缺点，最佳方法取决于输入向量的大小、字符串的长度以及可用的内存。