給定一個單詞序列，列印所有字謎

---

字謎 − 字謎是指透過重新排列另一個單詞或短語的字母形成的單詞或短語，通常只進行一次。下面給出了一些字謎的示例：

• 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++ 程式碼根據其排序後的表示形式有效地對給定單詞列表中的字謎進行分組。提供的解決方案效率很高，並且可以根據特定的用例輕鬆地進行調整。