トライ木 (Trie) で言葉の頭を調べる仕組みを作る｜コーディング面接問題

問題

言葉をしまっておき、あとから調べられる仕組み Trie を作ってください。次の 3 つの操作を持ちます。

insert(w) は、言葉 w をしまいます。何も返しません
search(w) は、言葉 w がまるごとしまってあれば真、無ければ偽を返します
startsWith(p) は、p で始まる言葉が 1 つでもしまってあれば真、無ければ偽を返します。p そのものがしまってある場合も真です

メソッドの名前は、JavaScript は上のまま、Python は starts_with のように小文字と下線、Go は Insert、Search、StartsWith と頭を大文字にします。Go では newTrie() で作ります。

言葉と頭はどれも英小文字 (a から z) だけで、長さは 1 以上 2000 以下です
操作は全部で 30000 回以下です

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

入力と出力の例

例 1

"cart" をしまったあとでは、"car" は頭としてはありますが、言葉としてはまだありません。"car" を足すと、言葉としても見つかります。

入力

ops = ["Trie", "insert",
  "search", "search",
  "startsWith", "insert",
  "search"]
args = [[], ["cart"],
  ["car"], ["cart"],
  ["car"], ["car"],
  ["car"]]

出力

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

例 2

頭が途中まで合っていても、次の文字の枝が無ければ偽です。

入力

ops = ["Trie", "insert",
  "insert", "search",
  "startsWith",
  "startsWith", "search"]
args = [[], ["sun"],
  ["sunday"], ["sund"],
  ["sund"], ["sat"],
  ["sunday"]]

出力

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

例 3

何もしまっていないうちは、どれを調べても偽です。

入力

ops = ["Trie", "search",
  "startsWith", "insert",
  "search", "startsWith"]
args = [[], ["a"], ["a"],
  ["a"], ["a"], ["a"]]

出力

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

面接での聞かれ方

面接では、入力補完や辞書の検索を例に出して渡されることが多いです。

「検索窓に打った頭から、候補があるかをすぐ答える仕組みを作ってください」
書き終えたあとに「言葉の集合 (set) を持つだけではだめですか？」「頭で始まる言葉を全部返すにはどうしますか？」と続けて聞かれます
「文字の種類が英小文字だけでなく、日本語も入るならどう持ちますか？」と、子の持ち方を聞かれることもあります

search と startsWith の違いは、最後の節に「ここで終わる言葉がある」という印があるかどうかだけです。書き始める前に、この 2 つの違いを口で確かめておくと迷いません。

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

まず考える手順

段 1

まずは素直に、しまった言葉を集合に入れる書き方を考えます。search は集合を引くだけで速く済みます。ところが startsWith は、しまった言葉を全部見て頭が合うかを比べることになり、言葉が多いと遅くなります。頭ごとに集合へ入れておく手もありますが、長い言葉ほど頭の数が増え、記憶をたくさん使います。

段 2

頭が同じ言葉は、途中まで同じ道を通る、と考えます。根から始めて、1 文字ごとに子へ進む木を作ります。"car" と "cart" は c、a、r まで同じ節を通り、"cart" だけが t の子へ進みます。同じ頭を何度しまっても、節は 1 回しか作りません。

段 3

節には、子の表 (文字から次の節へ) と、「ここで終わる言葉がある」という印の 2 つを持たせます。insert は、子が無ければ作りながら進み、最後の節に印を付けます。search と startsWith は、文字をたどって進み、途中で子が無ければ偽です。たどり切れたら、search は印を見て、startsWith はそのまま真を返します。

段 4

たどる部分は 2 つの操作で同じなので、1 つの関数にまとめます。たどり切れたら最後の節を、途中で切れたら無し (None、null、nil) を返す形にすると、search と startsWith はそれぞれ 2 行ほどで書けます。

解答

Python

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


class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, w):
        node = self.root
        for ch in w:
            kids = node.kids
            nxt = kids.get(ch)
            if nxt is None:
                nxt = TrieNode()
                kids[ch] = nxt
            node = nxt
        node.end = True

    def walk(self, s):
        node = self.root
        for ch in s:
            kids = node.kids
            if ch not in kids:
                return None
            node = kids[ch]
        return node

    def search(self, w):
        node = self.walk(w)
        if node is None:
            return False
        return node.end

    def starts_with(self, p):
        node = self.walk(p)
        return node is not None

JavaScript

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

class Trie {
  constructor() {
    this.root = new TrieNode();
  }

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

  walk(s) {
    let node = this.root;
    for (const ch of s) {
      node = node.kids.get(ch);
      if (node === undefined) {
        return null;
      }
    }
    return node;
  }

  search(w) {
    const node = this.walk(w);
    if (node === null) {
      return false;
    }
    return node.end;
  }

  startsWith(p) {
    const node = this.walk(p);
    return node !== null;
  }
}

Go

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

type Trie struct {
	root *trieNode
}

func newTrie() *Trie {
	return &Trie{&trieNode{}}
}

func (t *Trie) Insert(
	w string,
) {
	node := t.root
	for _, ch := range w {
		i := ch - 'a'
		if node.kids[i] == nil {
			node.kids[i] = &trieNode{}
		}
		node = node.kids[i]
	}
	node.end = true
}

func (t *Trie) walk(
	s string,
) *trieNode {
	node := t.root
	for _, ch := range s {
		node = node.kids[ch-'a']
		if node == nil {
			return nil
		}
	}
	return node
}

func (t *Trie) Search(
	w string,
) bool {
	node := t.walk(w)
	return node != nil && node.end
}

func (t *Trie) StartsWith(
	p string,
) bool {
	return t.walk(p) != nil
}

Go は文字が英小文字だけと決まっているので、子を 26 個の固定の並びで持ちます。ch - 'a' で、a を 0 番、z を 25 番に当てます。Python と JavaScript は、文字を鍵にした表で持ちます。

計算量

言葉や頭の長さを L とすると、どの操作も時間は O(L) です。1 文字ごとに子を 1 回引いて進むだけで、しまった言葉の数には関係しません
使う記憶は、しまった言葉の文字数の合計を S として O(S) です。頭が重なる言葉は節を分け合うので、実際はこれより少なく済みます
Go の書き方は、節ごとに 26 個の置き場を必ず持ちます。文字の種類が多いときは、Python や JavaScript のように表で持つほうが記憶を節約できます

よくある間違い

終わりの印を付け忘れる。節があるだけで真を返すと、"cart" しかしまっていないのに search("car") が真になります。言葉の終わりの節にだけ印を付け、search はそれを見ます
startsWith でも印を見てしまう。 逆に、頭の確かめで印まで見ると、"cart" があるのに startsWith("car") が偽になります。頭はたどり切れたかどうかだけで決まります
調べるときに節を作ってしまう。 search の中で、無い子を作りながら進むと、調べただけで木が育ちます。作るのは insert だけにし、調べる側は無ければすぐ偽を返します

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

class Trie: def __init__(self): # ここに持つ物を書きます pass def insert(self, w): # ここに書きます pass def walk(self, s): # ここに書きます pass def search(self, w): # ここに書きます pass def starts_with(self, p): # ここに書きます pass # 「実行」を押すと、下の行が動きます obj = Trie() print(obj.insert("cart"))

トライ木 (Trie) で言葉の頭を調べる仕組みを作る

問題