题目描述补充

题目：实现一个前缀树（Trie，又称字典树、单词查找树或键树），用于高效存储和检索字符串数据集中的键。前缀树是一种树形数据结构，其中的每个节点代表字符串中的一个字符。树的根节点不包含字符，除根节点外的每个节点都包含一个字符。从根节点到某个节点的路径上的字符连接起来，就是该节点对应的字符串。前缀树支持以下几种基本操作：

1. 插入：向前缀树中插入一个新的字符串。
2. 搜索：在前缀树中搜索一个完整的字符串。
3. 前缀搜索：在前缀树中搜索一个字符串的前缀，返回所有以该前缀开头的字符串。

示例代码

以下是使用 PHP、Python 和 JavaScript 实现的前缀树的基本框架和示例代码。

PHP 示例

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

    public function __construct() {
        $this->children = [];
        $this->isEndOfWord = false;
    }
}

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++) {
            $char = $word[$i];
            if (!isset($node->children[$char])) {
                $node->children[$char] = new TrieNode();
            }
            $node = $node->children[$char];
        }
        $node->isEndOfWord = true;
    }

    // 搜索字符串
    public function search($word) {
        $node = $this->root;
        for ($i = 0; $i < strlen($word); $i++) {
            $char = $word[$i];
            if (!isset($node->children[$char])) {
                return false;
            }
            $node = $node->children[$char];
        }
        return $node->isEndOfWord;
    }

    // 前缀搜索
    public function startsWith($prefix) {
        $node = $this->root;
        for ($i = 0; $i < strlen($prefix); $i++) {
            $char = $prefix[$i];
            if (!isset($node->children[$char])) {
                return false;
            }
            $node = $node->children[$char];
        }
        return true;
    }
}

// 使用示例
$trie = new Trie();
$trie->insert("apple");
echo $trie->search("apple") ? "Found" : "Not found";  // 输出 "Found"
echo $trie->startsWith("app") ? "Starts with 'app'" : "Not starts 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.root
        for char in word:
            if char not in node.children:
                return False
            node = node.children[char]
        return node.is_end_of_word

    def startsWith(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

# 使用示例
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.root;
        for (let char of word) {
            if (!node.children[char]) {
                return false;
            }
            node = node.children[char];
        }
        return node.isEndOfWord;
    }

    startsWith(prefix) {
        let node = this.root;
        for (let char of prefix) {
            if (!node.children[char]) {
                return false;
            }
            node = node.children[char];
        }
        return true;
    }
}

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

码小课

码小课网站中有更多关于算法和数据结构的内容分享，包括前缀树（Trie）的深入解析和进阶应用，欢迎大家学习交流。