C++で文字列配列内のアナグラムのペアをすべて検出・出力する方法

この記事では、文字列の配列が与えられたとき、その配列に含まれるアナグラム（アナグラム関係にある文字列のペア）をすべて見つけて出力する方法を、C++のサンプルコードとともに解説します。

アナグラムとは？

アナグラムとは、ある文字列の文字を並べ替えることで作られる別の文字列のことです。たとえば「hello」と「lolhe」は、使用する文字とその個数が完全に一致しているため、互いにアナグラムの関係にあります。

問題の例

具体的な入力と出力の例を見てみましょう。

入力: array = {"hello", "hrdef", "from", "lohel", "morf"}
出力: [hello, lohel], [from, morf]

この例では、「hello」と「lohel」、「from」と「morf」がそれぞれアナグラムのペアとして検出されています。

解法のアプローチ

最もシンプルな解法は、二重ループ（ネストしたループ）を使う方法です。

• 外側のループで配列を走査し、基準となる文字列を選択します。
• 内側のループで、残りの各文字列と比較し、アナグラムかどうかを判定します。

アナグラムの判定には、各文字の出現回数をカウントする配列（サイズ256のカウント配列）を使用します。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]<<" と "<<arr[j]<<" はアナグラムです。\n";
}

int main(){
    string arr[] = {"hello", "hrdef", "from", "lohel", "morf"};
    int n = sizeof(arr)/sizeof(arr[0]);
    printAnagrams(arr, n);
    return 0;
}

実行結果

hello と lohel はアナグラムです。
from と morf はアナグラムです。

計算量と最適化のポイント

この解法は理解しやすい一方で、効率面では改善の余地があります。文字列の数を n、文字列の長さを m とすると、すべてのペアを比較するため時間計算量は O(n² × m) となります。

より効率化するための工夫として、以下の方法が考えられます。

• 文字列をソートして比較する： 各文字列の文字をソートすると、アナグラム同士は必ず同じ文字列になります。ソート済みの文字列をキーとしてハッシュマップ（unordered_map）に格納すれば、グループ化を O(n × m log m) で実現できます。
• 正規化キーを事前計算する： 各文字列の文字カウントをあらかじめ計算しておくことで、ペア比較を高速化できます。

データ量が多い場合は、ソートやハッシュマップを活用したアプローチを採用することで、大幅なパフォーマンス向上が期待できます。

まとめ

本記事では、C++を用いて文字列配列内のアナグラムペアを検出する基本的な手法を紹介しました。二重ループによるシンプルな実装から、ソートやハッシュマップを使った最適化まで、状況に応じて適切な手法を選択することが重要です。