JavaScriptでアナグラムの単語をグループ化する方法

アナグラムとは

同じ文字を別の順序に並べ替えることで互いに作り出せる2つの単語やフレーズは、互いの「アナグラム（Anagram）」と呼ばれます。たとえば、「rat」と「tar」はどちらも r・a・t の3文字で構成されているため、互いのアナグラムです。

本記事では、アナグラムの文字列を含む可能性がある文字列の配列を受け取り、すべてのアナグラムを個別のサブ配列にグループ化して、その新しい配列を返すJavaScript関数の実装方法を解説します。

期待される入出力

たとえば、入力配列が次の場合：

const arr = ['rat', 'jar', 'tar', 'raj', 'ram', 'arm', 'mar', 'art'];

出力配列は次のようになります：

const output = [
    ['rat', 'tar', 'art'],
    ['jar', 'raj'],
    ['ram', 'arm', 'mar']
];

実装コード

以下が実際のコードです：

const arr = ['rat', 'jar', 'tar', 'raj','ram', 'arm', 'mar', 'art'];
const groupSimilarWords = (arr = []) => {
    if (arr.length === 0){
        return arr;
    };
    const map = new Map();
    for(let str of arr){
        let sorted = [...str];
        sorted.sort();
        sorted = sorted.join('');
        if(map.has(sorted)){
            map.get(sorted).push(str);
        }else{
            map.set(sorted, [str])
        };
    };
    return [...map.values()];
};
console.log(groupSimilarWords(arr));

アルゴリズムの解説

このアプローチのポイントは、各文字列を「文字をソートした結果」をキーとしてMapに登録することです。アナグラム同士は文字をソートすると必ず同一の文字列になるため、それをキーにすれば自然な形でグループ化できます。

1. 入力配列が空の場合は、そのまま空の配列を返します。
2. 各文字列に対して、スプレッド構文 [...str] で1文字ずつ分解し、sort() でソートした後、join('') で連結してキーを生成します。
3. Mapにそのキーがすでに存在すれば既存の配列へ追加し、存在しなければ新しいエントリを作成します。
4. 最後に map.values() をスプレッド展開して、グループ化されたサブ配列の配列として返します。

出力結果

コンソールには以下のように出力されます：

[ [ 'rat', 'tar', 'art' ], [ 'jar', 'raj' ], [ 'ram', 'arm', 'mar' ] ]