【JavaScript】連結して回文になる単語ペアを配列からすべて見つける方法

問題の概要

一意な単語（重複のない文字列）が格納された配列を受け取るJavaScript関数を作成します。

この関数は、配列内の2つの単語を連結したときに回文（前から読んでも後ろから読んでも同じ文字列）になる、すべてのインデックスペア [i, j] を配列として返す必要があります。

ここで重要なのは、順序が意味を持つという点です。たとえば (i, j) のペアでは「i番目の単語 + j番目の単語」の順で連結されるため、(j, i) も別の候補としてチェックする必要があります。

実装コード

以下は、二重ループですべてのペアを検証するシンプルな実装例です。

const arr = ["abcd", "dcba", "lls", "s", "sssll"];
const findPairs = (arr = []) => {
    const res = [];
    for ( let i = 0; i < arr.length; i++ ){
        for ( let j = 0; j < arr.length; j++ ){
            if (i !== j) {
                // 単語を連結
                const k = `${arr[i]}${arr[j]}`;
                // 連結結果を反転
                const l = [...k].reverse().join('');
                // 元の文字列と反転後の文字列が一致すれば回文
                if (k === l)
                    res.push([i, j]);
            }
        };
    };
    return res;
};
console.log(findPairs(arr));

コードのポイント

• 自己結合の除外： i !== j の条件により、同じ単語どうしの組み合わせをスキップしています。
• 反転処理： スプレッド構文 [...k] を使うことで、サロゲートペアを含む文字列でも安全に1文字ずつ分割できます。
• 計算量： 全ペアを調べるため時間計算量は O(n² × m)（m は平均的な単語長）となります。単語数が非常に多い場合は、ハッシュマップを活用した O(n × m²) の最適化手法もあります。

出力結果

[ [ 0, 1 ], [ 1, 0 ], [ 2, 4 ], [ 3, 2 ] ]

結果の解説

• [0, 1]："abcd" + "dcba" → "abcddcba"（回文）
• [1, 0]："dcba" + "abcd" → "dcbaabcd"（回文）
• [2, 4]："lls" + "sssll" → "llssssll"（回文）
• [3, 2]："s" + "lls" → "slls"（回文）

このように、連結後に回文となるすべてのインデックスペアが正しく取得できています。単純な総当たり方式ですが、ロジックが明快で理解しやすいため、まず基本形として押さえておくとよいでしょう。