C++で指定された文字列配列のアナグラムのすべてのペアを出力します

この問題では、文字列の配列が与えられ、その配列のアナグラムのすべてのペアを出力する必要があります。

アナグラム 別の文字列の文字を再配置することによって形成される文字列です。 Like − hello and lolhe

問題を理解するために例を見てみましょう-

Input: array = {“hello”, “hrdef”, “from”, “lohel”, “morf”}.
Output: [hello, lohel] , [from , morf]

この問題を解決するために、ループのネストを使用します。 2つのネストされたループが必要です。外側のループは配列をトラバースして要素を選択します。ネストされたループは、各文字列をチェックし、それらがアナグラムであるかどうかをチェックします。

例

そのアルゴリズムを実装するプログラムを見てみましょう-

#include <iostream>
using namespace std;
#define NO_OF_CHARS 256
bool isAnagramString(string str1, string str2){
   int count[NO_OF_CHARS] = {0};
   int i;
   for (i = 0; str1[i] && str2[i]; i++){
      count[str1[i]]++;
      count[str2[i]]--;
   }
   if (str1[i] || str2[i])
      return false;
   for (i = 0; i < NO_OF_CHARS; i++)
      if (count[i])
         return false;
      return true;
}
void printAnagrams(string arr[], int n){
   for (int i = 0; i < n; i++)
      for (int j = i+1; j < n; j++)
         if (isAnagramString(arr[i], arr[j]))
            cout<<arr[i]<<" and "<<arr[j]<<" are anagrams.\n";
}
int main(){
   string arr[] = {"hello", "hrdef", "from", "lohel", "morf"};
   int n = sizeof(arr)/sizeof(arr[0]);
   printAnagrams(arr, n);
   return 0;
}

出力

hello and lohel are anagrams.
from and morf are anagrams.

このソリューションは非常に理解しやすいですが、効率は劣ります。そのため、ソリューションをより効果的にするために、ソリューションにいくつかの最適化を行うことができます。文字列を含む配列をソートすることでそれを行うことができます。このソートされた配列により、アナグラムの検索が容易になります。