Sui Xin's Blog

[LeetCode]208. 实现 Trie (前缀树)（Implement Trie (Prefix Tree)）

Posted on In Disqus:

题目描述

实现一个 Trie (前缀树)，包含 insert, search, 和 startsWith 这三个操作。

示例:

Trie trie = new Trie();

trie.insert(“apple”);
trie.search(“apple”); // 返回 true
trie.search(“app”); // 返回 false
trie.startsWith(“app”); // 返回 true
trie.insert(“app”);
trie.search(“app”); // 返回 true

说明:

  • 你可以假设所有的输入都是由小写字母 a-z 构成的。
  • 保证所有输入均为非空字符串。

解题思路

前缀树的基本性质：

  1. 根节点不包含字符，除根节点外的每一个子节点都包含一个字符。
  2. 从根节点到某一个节点，路径上经过的字符连接起来，为该节点对应的字符串。
  3. 每个节点的所有子节点包含的字符互不相同。

即构建一个多叉树，根结点没有值，其余每个节点有三个属性：value，is_end_word，children。用于存储该结点的值、是否为某个单词的结尾、孩子结点集。

代码

Python 3.6

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
class Node(object):
    """docstring for Node"""
    def __init__(self, value=None, is_end_word=False):
        self.value = value
        self.is_end_word = is_end_word
        self.children = []


class Trie:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.root = Node(value="<SOW>")

    def add_child(self, root, value, is_end=False):
        for child_node in root.children:
            if child_node.value == value:
                if is_end:
                    child_node.is_end_word = True
                return child_node
        cur_node = Node(value=value, is_end_word=is_end)
        root.children.append(cur_node)
        return cur_node

    def insert(self, word: str) -> None:
        """
        Inserts a word into the trie.
        """
        cur = self.root
        for idx, char in enumerate(word):
            is_end = True if idx == len(word) - 1 else False
            cur = self.add_child(cur, char, is_end)

    def search(self, word: str) -> bool:
        """
        Returns if the word is in the trie.
        """
        cur = self.root
        for idx, char in enumerate(word):
            for cur_child in cur.children:
                if cur_child.value == char:
                    if idx == len(word) - 1:
                        return True if cur_child.is_end_word else False
                    else:
                        cur = cur_child
                        break
            else:
                return False

    def startsWith(self, prefix: str) -> bool:
        """
        Returns if there is any word in the trie that starts with the given prefix.
        """
        cur = self.root
        for idx, char in enumerate(prefix):
            for cur_child in cur.children:
                if cur_child.value == char:
                    if idx == len(prefix) - 1:
                        return True
                    else:
                        cur = cur_child
                        break
            else:
                return False

Related Posts