トライ木と深さ優先探索で文字の盤面から言葉を全部探す

文字の盤面の上下左右をたどって作れる言葉を、候補の一覧から全部探して、辞書の順に返します。候補をトライ木にまとめ、盤面を 1 回たどるあいだに全部の候補を同時に調べる練習です。

海外で定番の問題リスト 4 本には入っていません

問題

英小文字の盤面 board と、言葉の一覧 words を受け取ります。盤面で作れる言葉を words の中から全部探し、辞書の順 (a から z の順) に並べて返す関数を書いてください。

board は文字列の並びで、1 つの文字列が盤面の 1 行です。board[r][c] が r 行 c 列のマスの文字です
言葉は、あるマスから始めて、上下左右に隣り合うマスへ 1 つずつ進み、通ったマスの文字を順に読んで作ります。斜めには進めません
1 つの言葉の中で、同じマスを 2 回使うことはできません
words の中に同じ言葉は 2 回出てきません。見つかった言葉は、作り方が何通りあっても 1 回だけ答えに入れます
1 つも作れなければ、空の並び [] を返します
盤面は 1 行以上 12 行以下、1 列以上 12 列以下です。words は 1 個以上 3000 個以下で、どの言葉も 1 字以上 10 字以下の英小文字です

入力と出力の例

例 1

文字の盤面の言葉探しのパズルです。盤面は 3 行 4 列で、上の行から cats、arep、tone と並びます。cat は左上から右へ、tone はいちばん下の行を左から右へ読みます。step は右上の s から左の t、下の e、右の p と曲がって読みます。art は、r の隣に t が無いので作れません。

board = ["cats", "arep", "tone"] words = ["cat", "car", "art", "tone", "pet", "seat", "rot", "step"]

["car", "cat", "pet", "rot", "step", "tone"]

例 2

2 行 3 列の盤面です。god は上の行を右から左へ、dear は d から下の e、右の a、右の r と読みます。read と red は、r の隣に e が無いので作れません。

board = ["dog", "ear"] words = ["god", "dear", "read", "red"]

["dear", "god"]

例 3

aba は、a のマスを 2 回使わないと作れません。

board = ["ab"] words = ["aba", "ab", "b"]

["ab", "b"]

面接での聞かれ方

トライ木とバックトラックを組み合わせる難しい問題として、シニアの面接で出ます。

「盤面から、一覧にある言葉を全部探してください」
言葉を 1 つだけ探す問題 (盤面の単語探し) を解いたあとの続きとして出されることがよくあります。言葉ごとに盤面を探すと、言葉の数だけ時間がかかります
「見つけた言葉の枝をトライ木から外すと、何が速くなりますか？」と、枝を刈る工夫を聞かれることがあります

シニアの問題なので、候補をトライ木にまとめて 1 回のたどりで全部を同時に調べる発想と、戻るときにマスの印を外すバックトラックを、正しく組み合わせられるかが見られます。

ヒント

まだ開いていません

付箋は 4 枚。下の段ほど答えに近づきます

ヒント 2
ヒント 3
ヒント 4答えに近い

アルゴリズムのチートシートの「ハッシュマップ」に、この型の要点を表とコードでまとめています。

ハッシュは、値から番地を計算して、探す手間をほぼ 1 回にする仕組みです。重複や回数の問題は、この形で解けます。

まず考える手順

段 1

まずは素直に、言葉を 1 つずつ取り出し、盤面の全部のマスから深さ優先探索で探す書き方を考えます。動きますが、言葉が 3000 個あると、同じ盤面を 3000 回たどります。cat と car のように頭が同じ言葉も、別々に探し直します。

段 2

言葉を全部トライ木に入れます。言葉の終わりの節には、その言葉そのものを持たせます。こうすると、盤面をたどるときに「ここまで読んだ文字で始まる言葉が、まだあるか」をトライ木の節 1 つで分かります。

段 3

盤面の各マスから深さ優先探索を始め、トライ木の根から一緒に進みます。マスの文字に当たる子がトライ木に無ければ、その先に言葉は無いので戻ります。子があれば進み、その節が言葉の終わりなら答えに足します。

段 4

進むときはマスに「使った」の印を付け、上下左右を調べ終えて戻るときに印を外します。見つけた言葉は節から外し、同じ言葉を 2 回足さないようにします。最後に答えを辞書の順に並べ替えます。

解答

Python

def word_search_grid(
    board, words
):
    root = {}
    for w in words:
        node = root
        for ch in w:
            if ch not in node:
                node[ch] = {}
            node = node[ch]
        node["$"] = w
    rows = len(board)
    cols = len(board[0])
    seen = set()
    found = []

    def dfs(r, c, node):
        if not 0 <= r < rows:
            return
        if not 0 <= c < cols:
            return
        if (r, c) in seen:
            return
        ch = board[r][c]
        node = node.get(ch)
        if node is None:
            return
        if "$" in node:
            word = node.pop("$")
            found.append(word)
        seen.add((r, c))
        dfs(r + 1, c, node)
        dfs(r - 1, c, node)
        dfs(r, c + 1, node)
        dfs(r, c - 1, node)
        seen.remove((r, c))

    for r in range(rows):
        for c in range(cols):
            dfs(r, c, root)
    return sorted(found)

JavaScript

function wordSearchGrid(
  board, words
) {
  const root = new Map();
  for (const w of words) {
    let node = root;
    for (const ch of w) {
      if (!node.has(ch)) {
        node.set(ch, new Map());
      }
      node = node.get(ch);
    }
    node.set("$", w);
  }
  const rows = board.length;
  const cols = board[0].length;
  const seen = board.map(
    () => Array(cols)
      .fill(false)
  );
  const found = [];
  const dfs = (r, c, node) => {
    if (r < 0 || c < 0
      || r >= rows || c >= cols
      || seen[r][c]) {
      return;
    }
    const next =
      node.get(board[r][c]);
    if (next === undefined) {
      return;
    }
    if (next.has("$")) {
      found.push(next.get("$"));
      next.delete("$");
    }
    seen[r][c] = true;
    dfs(r + 1, c, next);
    dfs(r - 1, c, next);
    dfs(r, c + 1, next);
    dfs(r, c - 1, next);
    seen[r][c] = false;
  };
  board.forEach((row, r) => {
    [...row].forEach((_, c) => {
      dfs(r, c, root);
    });
  });
  return found.sort();
}

Go

import "sort"

type tnode struct {
	next [26]*tnode
	word string
}

func wordSearchGrid(
	board []string,
	words []string,
) []string {
	root := &tnode{}
	for _, w := range words {
		n := root
		for _, ch := range w {
			i := ch - 'a'
			if n.next[i] == nil {
				n.next[i] = &tnode{}
			}
			n = n.next[i]
		}
		n.word = w
	}
	rows := len(board)
	cols := len(board[0])
	seen := make([][]bool, rows)
	for r := range seen {
		seen[r] = make([]bool, cols)
	}
	found := []string{}
	var dfs func(int, int, *tnode)
	dfs = func(
		r, c int, n *tnode,
	) {
		if r < 0 || c < 0 ||
			r >= rows || c >= cols ||
			seen[r][c] {
			return
		}
		n = n.next[board[r][c]-'a']
		if n == nil {
			return
		}
		if n.word != "" {
			found = append(
				found, n.word)
			n.word = ""
		}
		seen[r][c] = true
		dfs(r+1, c, n)
		dfs(r-1, c, n)
		dfs(r, c+1, n)
		dfs(r, c-1, n)
		seen[r][c] = false
	}
	for r := 0; r < rows; r++ {
		for c := 0; c < cols; c++ {
			dfs(r, c, root)
		}
	}
	sort.Strings(found)
	return found
}

Python と JavaScript のトライ木は、文字から子の節への辞書 (Map) で、言葉の終わりには $ の鍵で言葉そのものを持たせます。盤面の文字は英小文字だけなので、$ と重なりません。

計算量

時間は、いちばん悪いと O(m × n × 4 × 3^(L−1)) です。m × n はマスの数、L はいちばん長い言葉の字数で、1 つのマスから、来た方向を除く 3 方向へ L 字まで広がります。実際はトライ木に無い文字で早く戻るので、ずっと少なくなります
トライ木を作るのに、言葉の字数の合計 S に比例する時間と記憶を使います。たどる所の記憶は、使った印の O(m × n) と、再帰の深さの O(L) です

よくある間違い

言葉ごとに盤面を探す。動きますが、言葉が多いと同じ盤面を何度もたどります。頭が同じ言葉もまとめて調べられるトライ木を使います
戻るときに印を外し忘れる。 1 つの道で使ったマスが、別の道で使えなくなり、例 1 の tone のような言葉を見落とします
見つけた言葉を節から外さない。同じ言葉を別の道でもう一度見つけると、答えに 2 回入ります。外すか、集合で重なりを除きます
言葉の終わりで戻ってしまう。 car を見つけたところで止めると、card のように car で始まる長い言葉を見落とします。答えに足したあとも、続けて進みます

解答を動かした版 Python 3.14.7Node.js 24.22.1Go 1.24.2確認日 2026年11月8日

main.py

def word_search_grid(board: list[str], words: list[str]) -> list[str]:
    """
    Goal: 何を返すか

    idea1: まず思いつく案
    -> runtime: O(?)  space: O(?)

    idea2: もっと速い案
    -> runtime: O(?)  space: O(?)

    edge case: 空、1 つだけ、など
    """
    # ここに書きます
    pass


# 「実行」を押すと、この行の結果が出ます
print(word_search_grid(["cats", "arep", "tone"], ["cat", "car", "art", "tone", "pet", "seat", "rot", "step"]))

できているか「例で確かめる」を押すと、問題の例を全部この関数に渡して、通ったかをここに出します