JavaScriptで有効なワードスクエアを判定する方法を解説

ワードスクエアとは？

ワードスクエア（Word Square）とは、複数の単語を正方形のマス目状に並べ、横方向（行）にも縦方向（列）にも同じ単語が読めるように配置したものです。

例えば、次のような配置は有効なワードスクエアの一例です。

HEART
EMBER
ABUSE
RESIN
TREND

1行目を横に読むと「HEART」、1列目を縦に読んでも「HEART」となり、同様にすべての行と列が対応しています。

作成する関数の仕様

今回は、単語の配列を引数として受け取るJavaScript関数を実装します。入力された配列が有効なワードスクエアを構成している場合は true を、そうでない場合は false を返します。

たとえば、次のような配列が入力された場合を考えてみましょう。

const arr = [
  "abcd",
  "bnrt",
  "crmy",
  "dtye"
];

各行を縦に読み上げると、同じ単語が現れるため、出力は次のようになります。

const output = true;

コード例

実際の実装コードは以下のとおりです。

const findValidSquares = (arr = []) => {
  for (let i = 0; i < arr.length; i++) {
    for (let j = 0; j < arr[i].length; j++) {
      // 行と列の長さが揃っていない場合は無効
      if (j >= arr.length || i >= arr[j].length) {
        return false;
      }
      // 対称位置の文字が一致しない場合は無効
      if (arr[i][j] !== arr[j][i]) {
        return false;
      }
    }
  }
  return true;
};

const arr = [
  "abcd",
  "bnrt",
  "crm",
  "dt"
];

console.log(findValidSquares(arr));

この例では、各行の長さが異なる（4文字・4文字・3文字・2文字）不完全な形の配列を渡しても、埋まっている部分の対称性が保たれていれば true と判定されます。

アルゴリズムのポイント

• 対称性の確認： グリッド上の位置 [i][j] の文字と [j][i] の文字が常に一致していれば、その配列はワードスクエアとなります。
• 範囲外アクセスへの対策： 各行の長さが異なる場合もあるため、比較前に j >= arr.length や i >= arr[j].length のチェックを行い、安全に処理します。
• 計算量： すべてのマスを一度ずつ確認するため、時間計算量は O(N²) です。

実行結果

コンソールには次のように出力されます。

true