给定一个单词序列，打印所有字谜

---

字谜 − 字谜是指通过重新排列另一个单词或短语的字母形成的单词或短语，通常只进行一次。下面给出了一些字谜的示例：

• Top - Pot

• Silent - Listen

• Post - Stop

• Dog - God

问题陈述

给定一个单词数组 arr[]。对于给定的数组，打印所有字谜。

示例 1

输入

arr[] = {“star”, “god”, “vile”, “save”, “evil”, “care”, “arts”, “race”, “dog”, “vase”}

输出

arts star 
care race 
dog god 
evil vile 
save vase

解释

给定数组中的字谜是：

star - arts
god - dog
vile - evil
save - vase
care - race

示例 2

输入

arr[] = {“thing”, “top”, “inlets”, “pot”, “opt”, “listen”, “night”}

输出

inlets listen 
night thing 
opt pot top 

解释

给定数组中的字谜是：

thing - night
top - pot - opt
inlets - listen

方法 1：单词排序

解决问题的一种方法是对 arr[] 中的单词进行排序，并创建一个映射，其中键是排序后的单词，值是具有相同排序后单词的单词的索引。根据存储在原始数组中的索引打印字谜。

伪代码

function anagrams(arr: vector of strings) -> set of sets of strings
   initialize an empty set of sets called 'res'    
   create a copy of 'arr' called 'list'    
   for each word 's' in 'list'
      sort the characters of 's' in ascending order
      initialize an empty unordered map called 'map' (key: string, value: vector of integers)    
   for i = 0 to size of 'arr' - 1
      add the index 'i' to the vector associated with the sorted word 'list[i]' in 'map'    
   for each entry in 'map'
      initialize an empty set of strings called 'temp'        
      for each index 'i' in entry's value vector
         add 'arr[i]' to 'temp'        
      if size of 'temp' > 1
         add 'temp' to 'res'
      return 'res'

示例：C++ 实现

以下程序将所有字谜一起打印出来。

#include <iostream>
#include <string>
#include <vector>
#include <unordered_map>
#include <set>
#include <algorithm>
using namespace std;

// Function to group anangrams together from the input array
set<set<string>> anagrams(vector<string> const &arr){
   set<set<string>> res;
   vector<string> list(arr);
   // Sorting words
   for (string &s : list){
      sort(s.begin(), s.end());
   }
   // Pushing sorted words into map along with indices
   unordered_map<string, vector<int>> map;
   for (int i = 0; i < arr.size(); i++){
      map[list[i]].push_back(i);
   }
   for (auto itr : map){
      set<string> temp;
      for (int i : itr.second){
         temp.insert(arr[i]);
      }
      if (temp.size() > 1){
         res.insert(temp);
      }
   }
   return res;
}
int main(){
   vector<string> arr = {"thing", "top", "inlets", "pot", "opt", "listen", "night"};
   set<set<string>> res = anagrams(arr);
   for (set<string> r : res){
      for (string s : r){
         cout << s << ' ';
      }
      cout << endl;
   }
   return 0;
}

输出

inlets listen 
night thing 
opt pot top

时间复杂度 − O(N*K logK)，其中 N 是输入数组的大小，K 是字符串的平均长度。

空间复杂度 − O(N)

方法 2：使用 Multimap

为了在以上代码中实现高效的分组，我们将使用 multimap。Maultimap 提供高效的分组、恒定时间的插入、快速的查找、冲突处理和动态大小。

伪代码

function anagrams(arr: vector of strings) -> set of sets of strings
   res = empty set of sets of strings
    
   list = copy of arr
   for each s in list
      sort the characters of s in ascending order
    
   map = empty unordered multimap of string to integer
   for i = 0 to size of arr - 1
      insert the pair (list[i], i) into map
    
   itr = iterator pointing to the beginning of map
   while itr is not at the end of map
      temp = empty set of strings
        
      curr = copy of itr
      while itr is not at the end of map and itr's key is the same as curr's key
         add arr[itr's value] to temp
         move itr to the next element
        
      if size of temp > 1
         add temp to res
    
   return res

示例：C++ 实现

以下程序将所有字谜一起打印出来。

#include <iostream>
#include <string>
#include <vector>
#include <unordered_map>
#include <set>
#include <algorithm>
using namespace std;

// Function to group anangrams together from the input array
set<set<string>> anagrams(vector<string> const &arr){
   set<set<string>> res;
   vector<string> list(arr);
   // Sorting words
   for (string &s : list){
      sort(s.begin(), s.end());
   }
   unordered_multimap<string, int> map;
   for (int i = 0; i < arr.size(); i++){
      map.insert(make_pair(list[i], i));
   }
   auto itr = map.begin();
   while (itr != map.end()){
      set<string> temp;
      for (auto curr = itr; itr != map.end() && itr->first == curr->first; itr++){
         temp.insert(arr[itr->second]);
      }
      if (temp.size() > 1){
         res.insert(temp);
      }
   }
   return res;
}
int main(){
   vector<string> arr = {"thing", "top", "inlets", "pot", "opt", "listen", "night"};
   set<set<string>> res = anagrams(arr);
   for (set<string> r : res){
      for (string s : r){
         cout << s << ' ';
      }
      cout << endl;
   }
   return 0;
}

输出

inlets listen 
night thing 
opt pot top

时间复杂度 − O(N*K logK + N + N*M)，其中 N 是输入数组的大小，K 是字符串的平均长度。

空间复杂度 − O(N)

结论

总之，提供的 C++ 代码根据其排序后的表示形式有效地对给定单词列表中的字谜进行分组。提供的解决方案效率很高，并且可以根据特定的用例轻松地进行调整。