算法：给定一个单词序列，使用STL打印所有的字谜

给定一组单词，将所有的字谜一起打印出来。

例如,

Input: array = {"cat", "dog", "tac", "god", "act"}
output: cat tac act, dog god
Explanation: cat tac and act are anagrams 
and dog and god are anagrams as 
they have the same set of characters.

Input: array = {"abc", "def", "ghi"}
output: abc, def, ghi
Explanation: There are no anagrams in the array.

这些帖子在这里讨论了其他方法：

• 给定单词顺序, 将所有字谜打印在一起
• 给定单词顺序, 将所有字母组合在一起打印2

方法：这是使用C ++标准模板库的HashMap解决方案, 该库存储键值对。在哈希图中, 键将是字符的排序集合, 值将是输出字符串。当两个字谜的字符排序时, 它们将相似。现在,

1. 将矢量元素存储在HashMap中, 其中key为已排序的字符串。
2. 如果键相同, 则将字符串添加到HashMap(字符串向量)的值中。
3. 遍历HashMap并打印字谜字符串。

CPP

// CPP program for finding all anagram
// pairs in the given array
#include <algorithm>
#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;
 
// Utility function for
// printing anagram list
void printAnagram(
     unordered_map<string, vector<string> >& store)
{
     unordered_map<string, vector<string> >::iterator it;
     for (it = store.begin();
          it != store.end(); it++) {
         vector<string> temp_vec(it->second);
         int size = temp_vec.size();
         if (size > 1) {
             for ( int i = 0; i < size; i++) {
                 cout << temp_vec[i] << " " ;
             }
             cout << "\n" ;
         }
     }
}
 
// Utility function for storing
// the vector of strings into HashMap
void storeInMap(vector<string>& vec)
{
     unordered_map<string, vector<string> >
         store;
     for ( int i = 0; i < vec.size(); i++) {
 
         string tempString(vec[i]);
         sort(tempString.begin(), tempString.end());
 
         // Check for sorted string
         // if it already exists
         if (store.find(
                 tempString)
             == store.end()) {
             vector<string> temp_vec;
             temp_vec.push_back(vec[i]);
             store.insert(make_pair(
                 tempString, temp_vec));
         }
 
         else {
             // Push new string to
             // already existing key
             vector<string> temp_vec(
                 store[tempString]);
             temp_vec.push_back(vec[i]);
             store[tempString] = temp_vec;
         }
     }
 
     // print utility function for printing
     // all the anagrams
     printAnagram(store);
}
 
// Driver code
int main()
{
     // initialize vector of strings
     vector<string> arr;
     arr.push_back( "geeksquiz" );
     arr.push_back( "lsbin" );
     arr.push_back( "abcd" );
     arr.push_back( "forgeeksgeeks" );
     arr.push_back( "zuiqkeegs" );
     arr.push_back( "cat" );
     arr.push_back( "act" );
     arr.push_back( "tca" );
 
     // utility function for storing
     // strings into hashmap
     storeInMap(arr);
     return 0;
}

注意：在g++中使用-std=c++ 11标志编译以上程序

输出如下：

cat act tca 
lsbin forgeeksgeeks 
geeksquiz zuiqkeegs

复杂度分析：

• 时间复杂度：O(n * m(log m)), 其中m是单词的长度。
  需要一次遍历数组。
• 空间复杂度：O(n)。
  字符串中有n个单词。该映射需要O(n)空间来存储字符串。