给定一组单词,将所有的字谜一起打印出来。
例如,
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
- 将矢量元素存储在HashMap中, 其中key为已排序的字符串。
- 如果键相同, 则将字符串添加到HashMap(字符串向量)的值中。
- 遍历HashMap并打印字谜字符串。
// 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)空间来存储字符串。
推荐阅读
- 算法题(给定矩阵的所有行中的公共元素)
- Python MongoDB如何使用Update_many查询()
- 算法题(如何计算两个数组中的最大求和路径())
- Linux中如何使用userdel命令(用法示例)
- 电子邮件组成和传输协议介绍
- Java中如何实现用户定义的自定义异常()
- PHP如何使用Ds\Deque Capacity()函数(示例)
- 如何使用CSS使div height扩展其内容()
- 专家支招 检查与处理电脑ARP欺骗的办法