Problem 2.3: Trie (200pts)

Problem

A trie is a tree where every node's label is a single character. Starting from the root, we can traverse down the tree and record the characters we see along the way to form a word. For example, traversing the following tree can yield a few words: "a", "at", "ate", "ai", and "air".

      a
    / \
    t   i
  /     \
  e       r

Or formally,

trie = tree('a', [tree('t', [tree('e')]), tree('i', [tree('r')])])

In this problem, you need to implement a function has_path that checks whether a given word can be formed by the traversal process described above.

字典树（Trie，或称前缀树）是一种特殊的树，其中每个节点的标签（label）都是一个单个字符。从根节点开始，我们可以沿着树向下遍历，并记录沿途遇到的字符，从而形成一个单词。 例如，遍历下面的这棵树可以得到几个单词：“a”、“at”、“ate”、“ai” 和 “air”。

      a
     / \
    t   i
   /     \
  e       r

或者用形式化的定义表示：

trie = tree('a', [tree('t', [tree('e')]), tree('i', [tree('r')])])

在这个问题中，您需要实现一个函数 has_path，它检查一个给定的单词是否能通过上述描述的遍历过程形成。

def has_path(t, word):
    """Return whether there is a rooted path in a tree where the entries along the path
    spell out a particular word.

    >>> greetings = tree('h', [tree('i'),
    ...                        tree('e', [tree('l', [tree('l', [tree('o')])]),
    ...                                   tree('y')])])
    >>> print_tree(greetings)
    h
      i
      e
        l
          l
            o
        y
    >>> has_path(greetings, 'h')
    True
    >>> has_path(greetings, 'i')
    False
    >>> has_path(greetings, 'hi')
    True
    >>> has_path(greetings, 'hello')
    True
    >>> has_path(greetings, 'hey')
    True
    >>> has_path(greetings, 'bye')
    False
    """
    assert len(word) > 0, "no path for empty word."
    "*** YOUR CODE HERE ***"

Hints

Solutions

Generated by AI.

Generated by AI.

---

one-liner

def has_path(t, word):
    return label(t) == word[0] and (len(word) == 1 or any([has_path(i, word[1:]) for i in branches(t)]))