Medium

题目描述

Trie（发音类似 “try”）或者说前缀树是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补完和拼写检查。

请你实现 Trie 类：

  • Trie() 初始化前缀树对象。
  • void insert(String word) 向前缀树中插入字符串 word。
  • boolean search(String word) 如果字符串 word 在前缀树中，返回 true（即，在检索之前已经插入）；否则，返回 false。
  • boolean startsWith(String prefix) 如果之前已经插入的字符串 word 的前缀之一为 prefix，返回 true；否则，返回 false。

示例 1：

输入
["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
输出
[null, null, true, false, true, null, true]

解释
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

提示：

  • 1 <= word.length, prefix.length <= 2000
  • word 和 prefix 仅由小写英文字母组成
  • insert、search 和 startsWith 调用次数总计不超过 3 * 10^4 次

解题思路

解题思路

前缀树（Trie）是一种专门处理字符串的树形数据结构，其核心思想是利用字符串的公共前缀来减少查询时间。

数据结构设计： 每个Trie节点包含两个主要成分：

  1. 一个布尔值 isEnd，标记该节点是否为某个单词的结尾
  2. 一个子节点数组或哈希表，存储指向下一级字符的指针

核心操作实现：

  1. 插入操作：从根节点开始，逐个字符遍历。如果当前字符对应的子节点不存在，就创建新节点。遍历完成后，将最后一个节点的 isEnd 标记为 true。

  2. 搜索操作：同样从根节点开始遍历字符。如果途中遇到不存在的字符路径，直接返回 false。如果能遍历完整个单词，还需检查最后节点的 isEnd 标记。

  3. 前缀搜索：与完整搜索类似，但不需要检查 isEnd 标记，只要能遍历完整个前缀即可。

实现细节： 可以使用数组（适用于固定字符集）或哈希表来存储子节点。由于题目限定只有小写英文字母，使用大小为26的数组更加高效。

时间复杂度方面，所有操作都是 O(m)，其中 m 是字符串长度，这使得 Trie 在处理大量字符串查询时非常高效。

代码实现

class Trie {
private:
    struct TrieNode {
        TrieNode* children[26];
        bool isEnd;
        
        TrieNode() {
            for (int i = 0; i < 26; i++) {
                children[i] = nullptr;
            }
            isEnd = false;
        }
    };
    
    TrieNode* root;
    
public:
    Trie() {
        root = new TrieNode();
    }
    
    void insert(string word) {
        TrieNode* node = root;
        for (char c : word) {
            int index = c - 'a';
            if (node->children[index] == nullptr) {
                node->children[index] = new TrieNode();
            }
            node = node->children[index];
        }
        node->isEnd = true;
    }
    
    bool search(string word) {
        TrieNode* node = root;
        for (char c : word) {
            int index = c - 'a';
            if (node->children[index] == nullptr) {
                return false;
            }
            node = node->children[index];
        }
        return node->isEnd;
    }
    
    bool startsWith(string prefix) {
        TrieNode* node = root;
        for (char c : prefix) {
            int index = c - 'a';
            if (node->children[index] == nullptr) {
                return false;
            }
            node = node->children[index];
        }
        return true;
    }
};

class Trie:
    def __init__(self):
        self.children = {}
        self.is_end = False

    def insert(self, word: str) -> None:
        node = self
        for char in word:
            if char not in node.children:
                node.children[char] = Trie()
            node = node.children[char]
        node.is_end = True

    def search(self, word: str) -> bool:
        node = self
        for char in word:
            if char not in node.children:
                return False
            node = node.children[char]
        return node.is_end

    def startsWith(self, prefix: str) -> bool:
        node = self
        for char in prefix:
            if char not in node.children:
                return False
            node = node.children[char]
        return True

public class Trie {
    private class TrieNode {
        public TrieNode[] Children;
        public bool IsEnd;
        
        public TrieNode() {
            Children = new TrieNode[26];
            IsEnd = false;
        }
    }
    
    private TrieNode root;

    public Trie() {
        root = new TrieNode();
    }
    
    public void Insert(string word) {
        TrieNode node = root;
        foreach (char c in word) {
            int index = c - 'a';
            if (node.Children[index] == null) {
                node.Children[index] = new TrieNode();
            }
            node = node.Children[index];
        }
        node.IsEnd = true;
    }
    
    public bool Search(string word) {
        TrieNode node = root;
        foreach (char c in word) {
            int index = c - 'a';
            if (node.Children[index] == null) {
                return false;
            }
            node = node.Children[index];
        }
        return node.IsEnd;
    }
    
    public bool StartsWith(string prefix) {
        TrieNode node = root;
        foreach (char c in prefix) {
            int index = c - 'a';
            if (node.Children[index] == null) {
                return false;
            }
            node = node.Children[index];
        }
        return true;
    }
}

var Trie = function() {
    this.children = {};
    this.isEnd = false;
};

Trie.prototype.insert = function(word) {
    let node = this;
    for (let char of word) {
        if (!node.children[char]) {
            node.children[char] = new Trie();
        }
        node = node.children[char];
    }
    node.isEnd = true;
};

Trie.prototype.search = function(word) {
    let node = this;
    for (let char of word) {
        if (!node.children[char]) {
            return false;
        }
        node = node.children[char];
    }
    return node.isEnd;
};

Trie.prototype.startsWith = function(prefix) {
    let node = this;
    for (let char of prefix) {
        if (!node.children[char]) {
            return false;
        }
        node = node.children[char];
    }
    return true;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

操作时间复杂度空间复杂度
insertO(m)O(m)
searchO(m)O(1)
startsWithO(m)O(1)
总体空间复杂度-O(ALPHABET_SIZE × N × M)

其中 m 是字符串长度，N 是插入的字符串数量，M 是字符串的平均长度，ALPHABET_SIZE 是字符集大小（此处为26）。

相关题目