JavaScriptでマトリックス内の単語を検索する方法（DFS＋バックトラッキング）

問題の概要

文字の配列を要素とする2次元配列（マトリックス）を第1引数に、文字列を第2引数として受け取るJavaScript関数を作成する必要があります。

関数の役割は、マトリックス内に存在する文字の中から重複なく選んだ組み合わせによって、第2引数で渡された文字列が作れるかどうかを判定することです。具体的には、縦・横に隣接するセルをたどって目的の単語が完成するかを確認します。

そのような組み合わせが存在すればtrueを、存在しなければfalseを返します。

入力例

たとえば、入力の配列と文字列が次のようなケースを考えてみましょう。

const arr = [
  ['s', 'd', 'k', 'e'],
  ['j', 'm', 'o', 'w'],
  ['y', 'n', 'l']
];
const str = 'don';

このとき、期待される出力は次のとおりです。

const output = false;

「d」の上下左右に隣接するセルには「o」が存在しないため、「don」という単語は隣接セルのつながりとして成立しないからです。

サンプルコード

以下が実際のコードです。この種の問題は深さ優先探索（DFS）とバックトラッキングを組み合わせることで効率よく解くことができます。

const arr = [
    ['s', 'd', 'k', 'e'],
    ['j', 'm', 'o', 'w'],
    ['y', 'n', 'l']
];
const str = 'don';

const containsWord = (arr = [], str = '') => {
    if (arr.length === 0){
        return false;
    };
    const height = arr.length;
    const width = arr[0].length;
    const dirs = [[-1, 0], [0, 1], [1, 0], [0, -1]];

    const tryWord = (x, y, k) => {
        // 現在のセルが探している文字と一致しなければ失敗
        if (arr[x][y] !== str[k]) return false;
        // 最後の文字まで一致すれば成功
        if (k === str.length - 1) return true;

        arr[x][y] = '*'; // 訪問済みマーク（同じセルの再利用を防止）

        for (const [dx, dy] of dirs) {
            const i = x + dx;
            const j = y + dy;
            if (i >= 0 && i < height && j >= 0 && j < width) {
                if (tryWord(i, j, k + 1)) return true;
            }
        }

        arr[x][y] = str[k]; // 元に戻す（バックトラッキング）
        return false;
    };

    for (let i = 0; i < height; i++) {
        for (let j = 0; j < width; j++) {
            if (tryWord(i, j, 0)) return true;
        }
    }
    return false;
};

console.log(containsWord(arr, str));

コードのポイント

• 全マスを起点に探索：マトリックス上のすべてのセルを開始点として、それぞれから単語との一致を試みます。
• 4方向への移動：dirs配列で定義した上下左右の4方向へ再帰的に移動し、次の文字との一致を確認します。
• 訪問済みマーク：一度使用したセルは一時的に「*」に置き換え、同じパス内で同じセルが再利用されないようにします。
• バックトラッキング：その経路での探索が失敗した場合はセルの文字を元に戻し、別の経路を試せる状態に復元します。

出力結果

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

false