实际要解决的问题

Trie 树的数据结构

Trie树，即字典树，⼜称 单词查找树 或 键树，是⼀种树形结构，是一种哈希树的变种。典型应⽤是⽤于统计和排序大量的字符串(但不仅限于字符串)，所以经常被搜索引擎系统用于⽂本词频统计。

它的优点是:最大限度地减少无谓的字符串比较，查询效率比哈希表高。

PS：根节点不存储字符串。

Trie 树的核⼼心思想

Trie的核心思想是空间换时间。利⽤字符串的公共前缀来降低查询时间的开销以达到提⾼效率的目的。

代码定义：Java 版

static final int ALPHABET_SIZE = 256;

static class TrieNode {
    TrieNode[] children = new TrieNode[ALPHABET_SIZE];
    boolean isEndOfWord = false;

    TrieNode() {
        isEndOfWord = false;
        for (int i = 0; i < ALPHABET_SIZE; i++) {
            children[i] = null;
        }
    }
}

代码定义：Kotlin 版

const val ALPHABET_SIZE = 256

class TrieNode {
    var children = arrayOfNulls<TrieNode>(ALPHABET_SIZE)
    var isEndOfWord = false
}

代码定义：Python 版

Trie 树的基本性质

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

相关题目

208. 实现 Trie (前缀树)

212. 单词搜索 II

系统设计：search suggestion 搜索建议