Word Search Algorithm - DFS + Backtracking

問題概要

2次元文字グリッド内で指定された単語が存在するかを判定する問題です。単語は隣接するセル（上下左右）を順次辿って構成され、同じセルは1回しか使用できません。

制約条件

1 ≤ m, n ≤ 6 (グリッドサイズ)
1 ≤ word.length ≤ 15 (単語長)
英大文字・小文字のみ
同じセルは1回のみ使用可能

Example

Input: board = [["A","B","C","E"],
                ["S","F","C","S"],
                ["A","D","E","E"]],
       word = "ABCCED"
Output: true

アルゴリズム詳解

採用手法: DFS + バックトラッキング

深さ優先探索（DFS）とバックトラッキングを組み合わせ、各セルを開始点として目標単語と一致するパスを探索します。

アルゴリズムの流れ

Step 1: 全セルを開始点候補として検証

Step 2: 現在セルが対象文字と一致するかチェック

Step 3: 一致した場合、セルを訪問済みとしてマーク

Step 4: 4方向（上下左右）に対して再帰的に探索

Step 5: 探索完了後、マークを解除（バックトラッキング）

核となる最適化ポイント

インプレース状態管理: visited配列不要でメモリ効率化
早期終了: 不一致発見時の即座な返却
短絡評価: OR演算子による効率的な方向探索

実装コード

完全実装

from typing import List

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        m, n = len(board), len(board[0])
        word_len = len(word)

        def dfs(i: int, j: int, k: int) -> bool:
            # ベースケース: 単語完成
            if k == word_len:
                return True

            # 境界チェック
            if not (0 <= i < m and 0 <= j < n):
                return False

            # 文字一致チェック
            if board[i][j] != word[k]:
                return False

            # バックトラッキング処理
            tmp = board[i][j]
            board[i][j] = "#"  # 訪問済みマーク

            # 4方向探索（短絡評価）
            res = (
                dfs(i + 1, j, k + 1) or  # 下
                dfs(i - 1, j, k + 1) or  # 上
                dfs(i, j + 1, k + 1) or  # 右
                dfs(i, j - 1, k + 1)     # 左
            )

            # 状態復元
            board[i][j] = tmp
            return res

        # 全セルから開始点を試行
        for i in range(m):
            for j in range(n):
                if dfs(i, j, 0):
                    return True
        return False

核となる関数の詳細解説

# DFS関数の各部分解説

# 1. 成功条件：単語を完全に見つけた
if k == word_len:
    return True

# 2. 境界条件：グリッド外アクセス防止
if not (0 <= i < m and 0 <= j < n):
    return False

# 3. 一致条件：現在文字が目標文字と一致するか
if board[i][j] != word[k]:
    return False

# 4. 状態管理：訪問済みマークと復元
tmp = board[i][j]      # 元の値を保存
board[i][j] = "#"      # 訪問済みマーク
# ... 探索処理 ...
board[i][j] = tmp      # 状態復元（重要！）

アルゴリズム可視化

グリッド状態

A

B

C

E

S

F

C

S

A

D

E

探索単語: ABCCED

現在位置: -

探索深度: 0

実行ステップ

可視化を開始してください

計算量分析

時間計算量

O(m × n × 4^L)

m × n: 全セルを開始点として試行
4^L: 各ステップで最大4方向、最大L回の再帰
L: 単語の長さ（最大15）

空間計算量

O(L)

再帰スタック: 単語長Lに比例
visited配列不要: インプレース管理
メモリ効率: 最小限の追加メモリ

制約条件下での性能

制約 m, n ≤ 6 かつ word.length ≤ 15 において:

最悪ケース: 6 × 6 × 4^15 ≈ 3.86 × 10^10 演算
実際の性能: 早期終了とプルーニングにより大幅削減
実用性: 制約が小さいため十分高速

最適化による改善効果

# 最適化前：visited配列使用
visited = [[False] * n for _ in range(m)]  # O(m×n) 追加メモリ

# 最適化後：インプレース管理
tmp = board[i][j]      # O(1) 一時変数のみ
board[i][j] = "#"      # 既存配列を活用
# ... 処理 ...
board[i][j] = tmp      # 状態復元

# 短絡評価による早期終了
return (dfs(i+1,j,k+1) or dfs(i-1,j,k+1) or
        dfs(i,j+1,k+1) or dfs(i,j-1,k+1))  # いずれか成功で即終了