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

2021年3月30日09:54:59 发表评论 368 次浏览

``````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

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 (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
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;
}``````

``````cat act tca
lsbin forgeeksgeeks
geeksquiz zuiqkeegs``````

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