Pythonでグリッド内に指定した単語が存在するか確認する方法

文字が敷き詰められたグリッド(2次元のマトリックス)が与えられ、その中に指定した単語が存在するかどうかを確認する問題を考えてみましょう。単語は4つの方向、すなわち水平方向の左・右、垂直方向の上・下に沿って読める場合に「存在する」とみなします。見つかれば True を、見つからなければ False を返します。

たとえば、次のようなグリッドが与えられたとします。

この状態で input_str = 'python' を探すと、1列目を上から下へ p → y → t → h → o → n とたどることで単語が見つかるため、出力は True になります。

アルゴリズムの流れ

この問題は、深さ優先探索(DFS)とバックトラッキングを組み合わせて解くのが定番です。手順は以下の通りです。

• 関数 find_grid() を定義します。引数は matrix(グリッド)、input_str(探す単語)、row_pos(現在の行位置)、col_pos(現在の列位置)、row_count(行数)、col_count(列数)、degree(ここまでに一致した文字数)です。
  • degree が input_str の長さと等しい場合:すべての文字を一致させられたので True を返します。
  • row_pos または col_pos がグリッドの範囲外の場合:False を返します。
  • matrix[row_pos][col_pos] が input_str[degree] と一致する場合:
    • 現在の文字を一時変数 temp に保存し、そのセルを「#」に置き換えて、同じセルを二度使わないようにします。
    • 上下左右の4方向に対して find_grid() を再帰呼び出しし、その結果を論理和(OR)で結合します。
    • 探索後、セルを temp の値に戻して(バックトラッキング)、result を返します。
  • それ以外の場合:False を返します。
• メインの solve 関数では、まず input_str の長さが 行数 × 列数 を超えていれば False を返します。
• グリッド全体を走査し、matrix[row][col] が input_str[0](先頭文字)と一致するセルを起点として find_grid() を呼び出します。結果が True なら True を返します。
• どこから始めても見つからなければ False を返します。

実装例

理解を深めるために、実際のPythonコードを見てみましょう。

def find_grid(matrix, input_str, row_pos, col_pos, row_count, col_count, degree):
    if degree == len(input_str):
        return True
    if row_pos < 0 or col_pos < 0 or row_pos >= row_count or col_pos >= col_count:
        return False
    if matrix[row_pos][col_pos] == input_str[degree]:
        temp = matrix[row_pos][col_pos]
        # 同じセルを再訪しないよう、一時的に「#」でマークする
        matrix[row_pos] = matrix[row_pos][:col_pos] + '#' + matrix[row_pos][col_pos + 1:]
        result = (find_grid(matrix, input_str, row_pos - 1, col_pos, row_count, col_count, degree + 1) |
                  find_grid(matrix, input_str, row_pos + 1, col_pos, row_count, col_count, degree + 1) |
                  find_grid(matrix, input_str, row_pos, col_pos - 1, row_count, col_count, degree + 1) |
                  find_grid(matrix, input_str, row_pos, col_pos + 1, row_count, col_count, degree + 1))
        # バックトラッキング:セルを元の文字に戻す
        matrix[row_pos] = matrix[row_pos][:col_pos] + temp + matrix[row_pos][col_pos + 1:]
        return result
    else:
        return False


def solve(matrix, input_str, row_count, col_count):
    if len(input_str) > row_count * col_count:
        return False
    for row in range(row_count):
        for col in range(col_count):
            if matrix[row][col] == input_str[0]:
                if find_grid(matrix, input_str, row, col, row_count, col_count, 0):
                    return True
    return False


word_grid = ['pghsf', 'ykdgh', 'tkghi', 'hnsjs', 'ojfgh', 'nrtyu']
print(solve(word_grid, 'python', 6, 5))

入力

['pghsf', 'ykdgh', 'tkghi', 'hnsjs', 'ojfgh', 'nrtyu'], 'python'

出力

True

計算量と実装のポイント

各セルを起点に最大4方向へ再帰探索が広がるため、時間計算量は O(R × C × 4^L)(R:行数、C:列数、L:単語の長さ)となります。重要なのは、訪問済みのセルを一時的に「#」でマークし、再帰から戻るときに必ず元の文字へ復元するバックトラッキングの処理です。これにより、別の開始セルからの探索が常にクリーンな状態で行えるようになります。なお、Pythonの文字列はイミュータブル(変更不可)なので、セルのマークと復元にはスライスを使って新しい文字列を作り直す点にも注意してください。