マトリックス文字ボード内の単語をチェックするPythonプログラム

問題の概要

各セルに1文字が格納された行列（マトリックス）形式の文字ボードと、検索対象の文字列 word が与えられます。このとき、word がボード内で「左から右」または「上から下」の一方向に連続して現れるかどうかを判定するのが課題です。

入力例

検索する単語：“tip”

この場合の出力は True になります。実際、3列目を上から下に読むと「t → i → p」となり、"tip" が形成されていることが確認できます。

解決のアプローチ

この問題はシンプルな全探索（ブルートフォース）で効率よく解けます。手順は以下の通りです。

• ボードの各行について、行内の文字をすべて連結して1つの文字列を作成し、その中に検索対象の単語が含まれているかを確認します。含まれていれば True を返します。
• 次に、変数 i を 0 に初期化し、i がボードの行数未満である限り以下を繰り返します。
  • 各行の i 番目の文字を集めて、i 列目の文字列 j を作成します。
  • j の中に単語が含まれていれば True を返します。
  • i を 1 増やして次の列へ進みます。
• すべての行と列を調べても見つからなければ、False を返します。

実装例（Python）

それでは、以下の実装例を見て理解を深めましょう。

def solve(board, word):
   for i in board:
      i = "".join(i)
      if word in i:
         return True
   i = 0
   while i < len(board):
      j = "".join([col[i] for col in board])
      i += 1
      if word in j:
         return True

   return False

board = [["a","n","t","s"],["s","p","i","n"],["l","a","p","s"]]
word = "tip"
print(solve(board, word))

入力

[["a","n","t","s"],
["s","p","i","n"],
["l","a","p","s"]],
"tip"

出力

True

計算量の目安

R 行 C 列のボードの場合、すべての行と列を一度ずつ走査するため、時間計算量はおおむね O(R × C) です。空間計算量については、行・列ごとに一時的な文字列を生成するため、最大でも O(max(R, C)) 程度に抑えられます。斜め方向の探索が必要になる類似問題（Word Search など）ではバックトラッキングが使われますが、本問題のように直線方向のみを扱う場合は、このような文字列連結によるアプローチが最も簡潔です。