Amazon VO 面试题解析：Trie Tree / Prefix Tree 实现

Implement a trie (prefix tree) with the following methods:

Trie() initializes the trie object.

void insert(String word) inserts the string word into the trie.

int search(String word) returns the value associated with the key word if the word exists in the trie, otherwise returns -1.

bool startsWith(String prefix) returns true if there is any previously inserted word that starts with the given prefix, otherwise returns false.

这道题要求实现一个 Trie（字典树 / 前缀树），核心是把字符串按字符逐层存到树结构中，从而高效支持单词插入、完整单词查找以及前缀判断。通常可以用哈希表或固定大小数组保存子节点，并在节点中维护是否为单词结尾的信息；插入和查询都沿着字符逐步向下走，时间复杂度与字符串长度成正比。面试中重点考察的是对前缀树结构的理解，以及如何用它把字符串检索从“按整词比较”转化为“按路径匹配”。