JavaScriptで類似文字列のグループ数を求める方法

問題の概要

2つの文字列 str1 と str2 は、str1 の異なる位置にある2つの文字を入れ替えることで str2 と一致させられる場合、「類似(similar)」していると定義されます。また、2つの文字列が完全に等しい場合も類似しているとみなします。

例えば、"tars" と "rats" は類似しています(0番目と2番目の文字を入れ替えることで一致)。また "rats" と "arts" も類似しています。しかし "star" は "tars"、"rats"、"arts" のいずれとも類似していません。

これらの文字列は、類似性によって次の2つの連結グループを形成します。{"tars", "rats", "arts"} と {"star"} です。ここで注目すべきは、"tars" と "arts" は直接には類似していませんが、"rats" を介してつながっているため、同じグループに属するという点です。

形式的に言うと、各グループは「ある単語がそのグループに属するのは、グループ内の少なくとも1つの他の単語と類似している場合、かつその場合に限る」という性質を持ちます。

課題

配列 arr 内のすべての文字列が、互いにアナグラム(文字の並べ替え)の関係にあるとき、類似性に基づくグループがいくつ存在するかを求める関数を作成します。

アプローチのポイント

• 2つの文字列を比較し、異なる文字の位置がちょうど2つであれば類似していると判定できます。
• 既存の各グループに含まれる文字列と順番に比較し、類似するものが見つかればそのグループへ追加します。
• どのグループにもマッチしなければ、新しいグループとして登録します。

コード例

以下が実装コードです。

const arr = ["tars","rats","arts","star"];
const isSimilar = (str1, str2) => {
    const obj = {}
    let counter = 0
    for(let i=0; i< str1.length; i++){
        if(str1[i] !== str2[i]) { counter++ }
        obj[str1[i]] = str2[i]
    }
    return counter === 2? true : false
}
const similarStringGroup = (arr = []) => {
    const group = [[arr[0]]]
    for(let i=1; i<arr.length; i++){
        let match = false
        for(let j=0; j<group.length; j++){
            for(let k=0; k< group[j].length; k++){
                const booleanMatch = isSimilar(group[j][k], arr[i])
                if(booleanMatch) {
                    group[j].push(arr[i]);
                    match = true
                    break;
                }
            }
            if(match === true) { break }
        }
        if(match === false){ group.push([arr[i]]) }
    }
    return group.length
}
console.log(similarStringGroup(arr));

コードの解説

isSimilar 関数は、2つの文字列を先頭から1文字ずつ比較し、異なる位置の数をカウントします。このカウントがちょうど2であれば true(類似)、それ以外は false を返します。

similarStringGroup 関数では、最初の文字列を最初のグループの起点とし、残りの文字列を順番に処理します。各文字列について、既存の全グループ内の文字列と類似判定を行い、マッチすればそのグループに追加、どこにもマッチしなければ新しいグループを作成します。最終的にグループの総数を返します。

出力結果

コンソールへの出力は以下の通りです。

2

この結果から、{"tars", "rats", "arts"} と {"star"} の2つのグループが正しく検出されたことがわかります。