实现 Trie (前缀树)

题目要求

你需要实现一个 Trie 类，这个类将提供以下功能：

1. Trie()：构造函数，用于初始化前缀树对象。
2. void insert(String word)：将字符串 word 插入到前缀树中。
3. boolean search(String word)：检查字符串 word 是否存在于前缀树中。如果存在，返回 true；如果不存在，返回 false。
4. boolean startsWith(String prefix)：检查是否有任何已插入的字符串 word 有以 prefix 作为前缀的。如果有，返回 true；如果没有，返回 false。

解题思路

前缀树（Trie）是一种用于快速检索的树形数据结构，特别适合处理字符串集合。以下是实现 Trie 类的思路：

1. 初始化 (Trie())：

   • 创建 Trie 类的实例时，需要初始化根节点，这个根节点不包含任何字符，但通常会包含指向子节点的链接（可以使用数组或哈希表实现）。

2. 插入 (insert(String word))：

   • 从根节点开始，对于 word 中的每个字符，沿着树向下移动。
   • 检查当前字符是否已经作为子节点存在：
     • 如果存在，移动到该子节点，继续处理下一个字符。
     • 如果不存在，创建一个新的子节点，并将其与当前节点链接起来，然后移动到这个新节点。
   • 在单词的最后一个字符的节点上，标记这个节点代表一个单词的结束。

3. 搜索 (search(String word))：

   • 从根节点开始，对于 word 中的每个字符，沿着树向下移动。
   • 如果当前字符的子节点不存在，返回 false。
   • 如果所有字符都成功匹配，但最后的节点没有标记为一个单词的结束，也返回 false。
   • 如果所有字符都成功匹配，并且最后的节点标记为一个单词的结束，返回 true。

4. 前缀搜索 (startsWith(String prefix))：

   • 类似于 search 方法，但是不需要检查最后的节点是否标记为一个单词的结束。
   • 如果能够对于 prefix 中的每个字符都找到对应的子节点，即使最后的节点没有标记为一个单词的结束，也返回 true。
   • 如果在某个点上子节点不存在，返回 false。

注意，Trie 的每个节点可能需要一个标记来表示该节点是否为某个单词的结束，以及可能的 26 个指向子节点的链接（假设只处理小写英文字母）。这些链接可以用数组或哈希表来实现，数组通常有固定大小（例如，26 个英文字母），而哈希表的大小则可以动态变化，适应不同的情况。

Golang 版本

type TrieNode struct {
    children [26]*TrieNode
    isEnd    bool
}

type Trie struct {
    root *TrieNode
}

func Constructor() Trie {
    return Trie{root: &TrieNode{}}
}

func (this *Trie) Insert(word string) {
    node := this.root
    for _, ch := range word {
        index := ch - 'a'
        if node.children[index] == nil {
            node.children[index] = &TrieNode{}
        }
        node = node.children[index]
    }
    node.isEnd = true
}

func (this *Trie) Search(word string) bool {
    node := this.root
    for _, ch := range word {
        index := ch - 'a'
        if node.children[index] == nil {
            return false
        }
        node = node.children[index]
    }
    return node.isEnd
}

func (this *Trie) StartsWith(prefix string) bool {
    node := this.root
    for _, ch := range prefix {
        index := ch - 'a'
        if node.children[index] == nil {
            return false
        }
        node = node.children[index]
    }
    return true
}

这段代码定义了一个 Trie 类型，包含 Insert, Search, 和 StartsWith 方法，以及一个 TrieNode 类型来表示前缀树的每个节点。每个节点包含一个固定大小的 children 数组用于存储子节点的引用，以及一个 isEnd 布尔值来标记是否有单词在此结束。Constructor 函数用于初始化一个 Trie 实例。

C++版本

#include <vector>
#include <string>

class TrieNode {
public:
    bool isEnd;
    vector<TrieNode*> children;

    TrieNode() : isEnd(false), children(26, nullptr) {}
};

class Trie {
private:
    TrieNode* root;

public:
    /** Initialize your data structure here. */
    Trie() {
        root = new TrieNode();
    }

    /** Inserts a word into the trie. */
    void insert(string word) {
        TrieNode* node = root;
        for (char c : word) {
            if (node->children[c - 'a'] == nullptr) {
                node->children[c - 'a'] = new TrieNode();
            }
            node = node->children[c - 'a'];
        }
        node->isEnd = true;
    }

    /** Returns if the word is in the trie. */
    bool search(string word) {
        TrieNode* node = root;
        for (char c : word) {
            node = node->children[c - 'a'];
            if (node == nullptr) {
                return false;
            }
        }
        return node->isEnd;
    }

    /** Returns if there is any word in the trie that starts with the given prefix. */
    bool startsWith(string prefix) {
        TrieNode* node = root;
        for (char c : prefix) {
            node = node->children[c - 'a'];
            if (node == nullptr) {
                return false;
            }
        }
        return true;
    }
};

/**
 * Your Trie object will be instantiated and called as such:
 * Trie* obj = new Trie();
 * obj->insert(word);
 * bool param_2 = obj->search(word);
 * bool param_3 = obj->startsWith(prefix);
 */

这段 C++ 代码定义了一个 Trie 类和一个 TrieNode 类。TrieNode 类包含一个 isEnd 标志位和一个 children 向量，用于存储指向子节点的指针。Trie 类包含 insert, search, 和 startsWith 方法，用于在前缀树中插入单词、搜索单词和检查是否存在以某前缀开始的单词。构造函数 Trie() 初始化一个新的前缀树。

Python 版本

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end_of_word = False

class Trie:

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

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

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

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

# Your Trie object will be instantiated and called as such:
# obj = Trie()
# obj.insert(word)
# param_2 = obj.search(word)
# param_3 = obj.starts_with(prefix)

这段 Python 代码定义了一个 Trie 类和一个辅助的 TrieNode 类。TrieNode 类用于表示前缀树的每个节点，包含一个字典 children 来存储子节点，以及一个布尔值 is_end_of_word 来标记节点是否是某个单词的结尾。Trie 类包含 insert, search, 和 starts_with 方法，分别用于向前缀树中插入单词、搜索单词和检查是否存在以某前缀开始的单词。

Java 版本

class TrieNode {
    private TrieNode[] links;
    private final int R = 26;
    private boolean isEnd;

    public TrieNode() {
        links = new TrieNode[R];
    }

    public boolean containsKey(char ch) {
        return links[ch -'a'] != null;
    }

    public TrieNode get(char ch) {
        return links[ch -'a'];
    }

    public void put(char ch, TrieNode node) {
        links[ch -'a'] = node;
    }

    public void setEnd() {
        isEnd = true;
    }

    public boolean isEnd() {
        return isEnd;
    }
}

public class Trie {
    private TrieNode root;

    public Trie() {
        root = new TrieNode();
    }

    public void insert(String word) {
        TrieNode node = root;
        for (int i = 0; i < word.length(); i++) {
            char currentChar = word.charAt(i);
            if (!node.containsKey(currentChar)) {
                node.put(currentChar, new TrieNode());
            }
            node = node.get(currentChar);
        }
        node.setEnd();
    }

    private TrieNode searchPrefix(String word) {
        TrieNode node = root;
        for (int i = 0; i < word.length(); i++) {
            char curLetter = word.charAt(i);
            if (node.containsKey(curLetter)) {
                node = node.get(curLetter);
            } else {
                return null;
            }
        }
        return node;
    }

    public boolean search(String word) {
        TrieNode node = searchPrefix(word);
        return node != null && node.isEnd();
    }

    public boolean startsWith(String prefix) {
        TrieNode node = searchPrefix(prefix);
        return node != null;
    }
}

// Your Trie object will be instantiated and called as such:
// Trie obj = new Trie();
// obj.insert(word);
// boolean param_2 = obj.search(word);
// boolean param_3 = obj.startsWith(prefix);

这段 Java 代码定义了一个 Trie 类和一个 TrieNode 类。TrieNode 类包含一个 TrieNode 数组来存储链接到子节点的引用，一个布尔值 isEnd 来标记是否有单词在此结束。Trie 类包含 insert, search, 和 startsWith 方法，用于在前缀树中插入单词、搜索单词和检查是否存在以某前缀开始的单词。此外，还有一个辅助的 searchPrefix 方法，用于搜索整个单词或前缀在前缀树中的位置。

Rust 版本

#![allow(unused)]
fn main() {
const ALPHABET_SIZE: usize = 26;

struct TrieNode {
    children: [Option<Box<TrieNode>>; ALPHABET_SIZE],
    is_end_of_word: bool,
}

impl TrieNode {
    fn new() -> Self {
        TrieNode {
            children: Default::default(),
            is_end_of_word: false,
        }
    }
}

pub struct Trie {
    root: TrieNode,
}

impl Trie {
    pub fn new() -> Self {
        Trie {
            root: TrieNode::new(),
        }
    }

    pub fn insert(&mut self, word: String) {
        let mut node = &mut self.root;
        for c in word.chars() {
            let index = (c as usize) - ('a' as usize);
            node = node.children[index].get_or_insert_with(|| Box::new(TrieNode::new()));
        }
        node.is_end_of_word = true;
    }

    pub fn search(&self, word: String) -> bool {
        self.find(word).map_or(false, |node| node.is_end_of_word)
    }

    pub fn starts_with(&self, prefix: String) -> bool {
        self.find(prefix).is_some()
    }

    fn find(&self, prefix: String) -> Option<&TrieNode> {
        let mut node = &self.root;
        for c in prefix.chars() {
            match node.children[(c as usize) - ('a' as usize)] {
                Some(ref child) => node = child,
                None => return None,
            }
        }
        Some(node)
    }
}
}

这段 Rust 代码定义了一个 TrieNode 结构体，它包含一个固定大小的 children 数组，用于存储指向子节点的指针，以及一个 is_end_of_word 布尔值，用于标记节点是否是单词的结尾。Trie 结构体包含一个 root TrieNode，以及 insert、search 和 starts_with 方法，用于在前缀树中插入单词、搜索单词和检查是否存在以某前缀开始的单词。此外，还有一个私有的 find 方法，用于查找整个单词或前缀在前缀树中的位置。

总结

上面的解法展示了如何在不同的编程语言中实现一个前缀树（Trie）。每种语言的实现都遵循了相同的基本原理，但是具体的语法和数据结构的使用根据语言的特性有所不同。

• 共同点：所有实现都包含了三个主要的操作：

  1. insert：向前缀树中插入一个新的单词。
  2. search：搜索前缀树中是否存在一个完整的单词。
  3. startsWith：检查前缀树中是否有单词以给定的前缀开始。

  每个实现都使用了一个辅助的节点结构（TrieNode），该结构通常包含了一个指向子节点的数组（或映射）以及一个布尔值标记，用于表示是否有单词在该节点结束。

• 不同点：

  • Python：使用字典来存储子节点，以字符作为键。
  • Java：使用固定大小的数组来存储子节点，以字符的 ASCII 值减去 'a' 的 ASCII 值作为索引。
  • Rust：使用固定大小的数组，其中每个元素是 Option<Box<TrieNode>> 类型，这允许 Rust 以值的形式拥有节点并提供空值的选项。

每种语言的实现都遵循了前缀树的基本概念，但是在内存管理、类型系统和语法糖方面各有特色。例如，Rust 版本使用了 Option 和 Box 来处理可空的指针和堆分配的内存，而 Python 版本则利用了其动态类型和内置的字典类型来简化节点的子项管理。Java 版本则介于两者之间，使用了更传统的 OOP 方法和数组来管理节点的子项。