神秘序列
题目名称：神秘序列
知识点
- Trie字典树（前缀树）
- 最短唯一前缀
- 路径记录
题目描述
给定n个字符串，对于每个字符串，找到它的最短唯一前缀。
最短唯一前缀定义：
- 最短的、只有这个字符串使用的前缀
- 例如：如果词典中有"cat"、"car"、"card"，那么：
- "cat"的最短唯一前缀是"cat"（因为"ca"被"car"和"card"共享）
- "car"的最短唯一前缀是"car"（因为"ca"被共享）
- "card"的最短唯一前缀是"card"
要求：
- 使用Trie字典树存储所有字符串
- 记录每个节点被哪些字符串经过
- 找到第一个"只被当前字符串经过"的节点
输入格式
第一行包含一个整数 n，表示字符串的数量。 （1 ≤ n ≤ 1000）
接下来n行，每行一个字符串。 （字符串只包含小写字母，长度不超过50）
输出格式
输出n行，每行一个字符串，表示对应输入字符串的最短唯一前缀。
样例输入1
5
cat
car
card
dog
do
样例输出1
cat
car
card
dog
do
样例1说明：
- "cat"的前缀"cat"是唯一的（"car"和"card"的前缀是"ca"）
- "car"的前缀"car"是唯一的（"card"的前缀是"card"）
- "card"的前缀"card"是唯一的
- "dog"的前缀"dog"是唯一的
- "do"的前缀"do"是唯一的（虽然"dog"的前缀是"do"，但"do"本身是完整单词）
样例输入2
3
a
ab
abc
样例输出2
a
ab
abc
样例2说明：
- "a"的前缀"a"是唯一的
- "ab"的前缀"ab"是唯一的（"a"被"a"和"abc"共享）
- "abc"的前缀"abc"是唯一的
样例输入3
3
hello
world
hi
样例输出3
hello
world
hi
样例3说明：
- 三个字符串没有公共前缀，所以每个字符串的最短唯一前缀就是它本身
提示
- 插入时记录每个节点被哪些字符串经过（使用
pass[p].push_back(id)） - 查询时找到第一个
pass[p].size() == 1且pass[p][0] == id的节点 - 如果没有找到唯一前缀，返回整个字符串
- 时间复杂度：O(ns)，其中s是字符串平均长度
考察知识点总结
- ✅ Trie字典树的插入和查询
- ✅ 路径记录（记录节点被哪些字符串经过）
- ✅ 最短唯一前缀查找
- ✅ 字符串处理
难度评估
难度： ⭐⭐⭐⭐⭐（高）
适合： 学习Trie字典树的高级应用和路径记录技巧