トライ木で伏せ字の入った言葉を探す仕組みを作る｜コーディング面接問題

問題

言葉をしまっておき、伏せ字を含む形で探せる仕組み WordBook を作ってください。次の 2 つの操作を持ちます。

addWord(w) は、言葉 w をしまいます。何も返しません
search(w) は、しまった言葉のうち w に当てはまる物が 1 つでもあれば真、無ければ偽を返します。w の中の . は、どの 1 文字にも当たる伏せ字です。長さは同じでなければ当てはまりません

メソッドの名前は、JavaScript は上のまま、Python は add_word と search、Go は AddWord と Search です。Go では newWordBook() で作ります。

しまう言葉は英小文字 (a から z) だけ、探す言葉は英小文字と . だけです
長さはどれも 1 以上 25 以下です
探す言葉に入る . は、1 つの言葉につき 2 つまでです
操作は全部で 10000 回以下です

例は、呼ぶ操作の名前の並び ops と、それぞれに渡す引数の並び args で書きます。最初の "WordBook" は作るところです。出力は操作ごとの戻り値の並びで、作るところと addWord は null です。

入力と出力の例

例 1

"r.pe" は "rope" にも "ripe" にも当たります。"rop" は頭が合うだけで、言葉としてはありません。

入力

ops = ["WordBook", "addWord",
  "addWord", "search",
  "search", "search"]
args = [[], ["rope"],
  ["ripe"], ["r.pe"],
  ["rop"], ["..pe"]]

出力

[null, null, null, true,
 false, true]

例 2

伏せ字は 1 文字ちょうどに当たります。長さの違う言葉には当たりません。

入力

ops = ["WordBook", "addWord",
  "addWord", "search",
  "search", "search"]
args = [[], ["go"], ["gold"],
  ["g.."], ["g..d"], ["."]]

出力

[null, null, null, false,
 true, false]

例 3

何もしまっていないうちは、伏せ字だけでも当たりません。

入力

ops = ["WordBook", "search",
  "addWord", "search",
  "search"]
args = [[], ["."], ["a"],
  ["."], ["a"]]

出力

[null, false, null, true,
 true]

面接での聞かれ方

面接では、トライ木の基本を書けるかを確かめたうえで、伏せ字を足して出されることが多いです。

「辞書に言葉を足す操作と、. を伏せ字にして探す操作を作ってください」
書き終えたあとに「伏せ字が多いと、どこまで遅くなりますか？」「言葉を全部並べて比べる書き方と、どちらが速いですか？」と、計算量の見積もりを聞かれます
「* (何文字でも当たる伏せ字) も入れるとしたら、どう変わりますか？」と、形を広げて聞かれることもあります

伏せ字があると、たどる道が 1 本に決まりません。どの節を同時に候補として持つのか、その数がどこまで増えるのかを、書く前に言えることが求められます。

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

まず考える手順

段 1

まずは素直に、しまった言葉を全部並べておき、探すたびに 1 つずつ比べる書き方を考えます。長さが同じ言葉について、1 文字ずつ「同じか、伏せ字か」を見れば正しく動きます。ただ、言葉が n 個あれば、1 回探すたびに n 個全部を見ることになり、操作が多いと遅すぎます。

段 2

伏せ字が無ければ、トライ木で 1 文字ずつ子をたどるだけです。そこで、伏せ字の無い文字はいつもどおり 1 つの子へ進み、伏せ字のところだけは全部の子へ分かれて進む、と考えます。しまった言葉の数ではなく、探す言葉の長さと伏せ字の数で手間が決まるようになります。

段 3

分かれた道を 1 本ずつ再帰でたどる書き方もできますが、ここでは「いま当てはまっている節の集まり」を持ち、1 文字ごとに集まりを丸ごと次へ進めます。文字が決まっていれば各節の子を 1 つだけ、伏せ字なら各節の子を全部、次の集まりへ入れます。集まりが空になったら、その時点で偽です。

段 4

最後の文字まで進めたら、集まりの中に「ここで終わる言葉がある」印の付いた節が 1 つでもあれば真です。伏せ字は 2 つまでなので、集まりの大きさは多くても 26 × 26 = 676 です。言葉の数がいくら増えても、1 回の探索の手間はこの上限で押さえられます。

解答

Python

class BookNode:
    def __init__(self):
        self.kids = {}
        self.end = False


def step(nodes, ch):
    nxt = []
    for node in nodes:
        kids = node.kids
        if ch == ".":
            nxt += kids.values()
        elif ch in kids:
            nxt.append(kids[ch])
    return nxt


class WordBook:
    def __init__(self):
        self.root = BookNode()

    def add_word(self, w):
        node = self.root
        for ch in w:
            kids = node.kids
            nx = kids.get(ch)
            if nx is None:
                nx = BookNode()
                kids[ch] = nx
            node = nx
        node.end = True

    def search(self, w):
        cur = [self.root]
        for ch in w:
            cur = step(cur, ch)
            if not cur:
                return False
        for node in cur:
            if node.end:
                return True
        return False

JavaScript

class BookNode {
  constructor() {
    this.kids = new Map();
    this.end = false;
  }
}

function step(nodes, ch) {
  const nx = [];
  for (const node of nodes) {
    const kids = node.kids;
    if (ch === ".") {
      nx.push(...kids.values());
    } else if (kids.has(ch)) {
      nx.push(kids.get(ch));
    }
  }
  return nx;
}

class WordBook {
  constructor() {
    this.root = new BookNode();
  }

  addWord(w) {
    let node = this.root;
    for (const ch of w) {
      const kids = node.kids;
      let next = kids.get(ch);
      if (next === undefined) {
        next = new BookNode();
        kids.set(ch, next);
      }
      node = next;
    }
    node.end = true;
  }

  search(w) {
    let cur = [this.root];
    for (const ch of w) {
      cur = step(cur, ch);
      if (cur.length === 0) {
        return false;
      }
    }
    for (const node of cur) {
      if (node.end) return true;
    }
    return false;
  }
}

Go

type bookNode struct {
	kids [26]*bookNode
	end  bool
}

type WordBook struct {
	root *bookNode
}

func newWordBook() *WordBook {
	return &WordBook{&bookNode{}}
}

func (b *WordBook) AddWord(
	w string,
) {
	node := b.root
	for _, ch := range w {
		i := ch - 'a'
		if node.kids[i] == nil {
			node.kids[i] = &bookNode{}
		}
		node = node.kids[i]
	}
	node.end = true
}

func step(
	nodes []*bookNode, ch rune,
) []*bookNode {
	nx := []*bookNode{}
	for _, node := range nodes {
		if ch != '.' {
			kid := node.kids[ch-'a']
			if kid != nil {
				nx = append(nx, kid)
			}
			continue
		}
		kids := node.kids
		for _, kid := range kids {
			if kid != nil {
				nx = append(nx, kid)
			}
		}
	}
	return nx
}

func (b *WordBook) Search(
	w string,
) bool {
	cur := []*bookNode{b.root}
	for _, ch := range w {
		cur = step(cur, ch)
		if len(cur) == 0 {
			return false
		}
	}
	for _, node := range cur {
		if node.end {
			return true
		}
	}
	return false
}

step は、いま当てはまっている節の集まりを、1 文字分だけ先へ進めます。同じ節が 2 回入ることはありません。木では、どの節にも親が 1 つしか無いからです。

計算量

addWord は、言葉の長さを L として時間 O(L) です
search は、伏せ字の無い文字では集まりの大きさが増えず、伏せ字 1 つで多くても 26 倍になります。伏せ字が 2 つまでなので、集まりは 676 個までで、時間は O(676 × L)、つまり O(L) です。しまった言葉の数 n には関係しません
使う記憶は、木がしまった文字数の合計 S に比例して O(S)、search の集まりが多くても 676 個です
段 1 の全部比べる書き方は、1 回の search に O(n × L) かかります。言葉が 10000 個に近いと、この差が効いてきます

よくある間違い

最後に印を見ずに真を返す。集まりが空でないことだけで真にすると、"gold" しか無いのに "g.." が真になります。たどり切った節に、言葉の終わりの印があるかを見ます
伏せ字の数の上限を見落として計算量を言う。伏せ字が何個でもよいなら、集まりは 26 の何乗にも増えます。2 つまでという条件があるから O(L) と言える、と根拠まで添えて話します
再帰で書いて、文字列を切り出しながら渡す。残りの文字列を毎回切り出して渡すと、1 段ごとに写しを作り、長さの 2 乗の手間がかかります。位置の番号を渡すか、この解答のように集まりを進める形にします

解答を動かした版 Python 3.12.14Node.js 22.23.4Go 1.24.6確認日 2026年10月30日

class WordBook: def __init__(self): # ここに持つ物を書きます pass def add_word(self, w): # ここに書きます pass def search(self, w): # ここに書きます pass # 「実行」を押すと、下の行が動きます obj = WordBook() print(obj.add_word("rope"))

トライ木で伏せ字の入った言葉を探す仕組みを作る

問題