题目描述

实现一个 Trie（前缀树），也称为字典树或单词查找树，用于高效地存储和检索字符串数据集中的键。Trie 树是一种树形结构，其中的每个节点都代表一个字符串中的字符，从根节点到某一节点所经过的路径上所有字符连接起来，就是该节点对应的字符串。Trie 树常用于自动补全、拼写检查、IP 路由等领域。

Trie 树的基本操作：

1. 插入（Insert）：向 Trie 树中插入一个新的字符串。
2. 搜索（Search）：检查 Trie 树中是否存在一个完整的字符串。
3. 前缀搜索（StartsWith）：检查 Trie 树中是否存在某个前缀。

示例代码

PHP 实现

class TrieNode {
    public $children = [];
    public $isEndOfWord = false;

    public function __construct() {
        $this->children = array_fill(0, 26, null); // 假设只处理小写字母
    }
}

class Trie {
    private $root;

    public function __construct() {
        $this->root = new TrieNode();
    }

    // 插入
    public function insert($word) {
        $node = $this->root;
        for ($i = 0; $i < strlen($word); $i++) {
            $index = ord($word[$i]) - ord('a');
            if (!isset($node->children[$index])) {
                $node->children[$index] = new TrieNode();
            }
            $node = $node->children[$index];
        }
        $node->isEndOfWord = true;
    }

    // 搜索
    public function search($word) {
        $node = $this->searchPrefix($word);
        return $node !== null && $node->isEndOfWord;
    }

    // 前缀搜索
    public function startsWith($prefix) {
        return $this->searchPrefix($prefix) !== null;
    }

    // 辅助函数：搜索前缀
    private function searchPrefix($word) {
        $node = $this->root;
        for ($i = 0; $i < strlen($word); $i++) {
            $index = ord($word[$i]) - ord('a');
            if (!isset($node->children[$index])) {
                return null;
            }
            $node = $node->children[$index];
        }
        return $node;
    }
}

// 使用示例
$trie = new Trie();
$trie->insert("apple");
echo $trie->search("apple") ? "Found" : "Not found";  // 输出: Found
echo $trie->startsWith("app") ? "Starts with 'app'" : "Does not start with 'app'";  // 输出: Starts with 'app'

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.searchPrefix(word)
        return node is not None and node.is_end_of_word

    def startsWith(self, prefix: str) -> bool:
        return self.searchPrefix(prefix) is not None

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

# 使用示例
trie = Trie()
trie.insert("apple")
print(trie.search("apple"))  # 输出: True
print(trie.startsWith("app"))  # 输出: True

JavaScript 实现

class TrieNode {
    constructor() {
        this.children = {};
        this.isEndOfWord = false;
    }
}

class Trie {
    constructor() {
        this.root = new TrieNode();
    }

    insert(word) {
        let node = this.root;
        for (let char of word) {
            if (!node.children[char]) {
                node.children[char] = new TrieNode();
            }
            node = node.children[char];
        }
        node.isEndOfWord = true;
    }

    search(word) {
        let node = this.searchPrefix(word);
        return node !== null && node.isEndOfWord;
    }

    startsWith(prefix) {
        return this.searchPrefix(prefix) !== null;
    }

    searchPrefix(word) {
        let node = this.root;
        for (let char of word) {
            if (!node.children[char]) {
                return null;
            }
            node = node.children[char];
        }
        return node;
    }
}

// 使用示例
const trie = new Trie();
trie.insert("apple");
console.log(trie.search("apple"));  // 输出: true
console.log(trie.startsWith("app"));  // 输出: true

这些示例展示了如何在 PHP、Python 和 JavaScript 中实现 Trie 树，并提供了基本的插入、搜索和前缀搜索功能。在面试中，能够根据需求清晰、准确地编写出 Trie 树的实现代码，将体现出你的编程能力和数据结构知识的掌握程度。