算法(给定一个单词序列,使用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
【算法(给定一个单词序列,使用STL打印所有的字谜)】方法:这是使用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)空间来存储字符串。

    推荐阅读