神秘复合词
题目名称：神秘复合词
知识点
- Trie字典树（前缀树）
- 字符串分割
- 枚举算法
题目描述
给定一个词典（包含n个单词），判断每个单词是否是"复合词"。
复合词定义：
- 可以拆分成两个在词典中的单词
- 例如："catcar" = "cat" + "car"，如果"cat"和"car"都在词典中，则"catcar"是复合词
要求：
- 使用Trie字典树存储词典
- 枚举每个单词的所有可能的断点
- 判断左右两部分是否都在词典中
输入格式
第一行包含一个整数 n，表示词典中单词的数量。 （1 ≤ n ≤ 1000）
接下来n行，每行一个字符串，表示词典中的单词。 （字符串只包含小写字母，长度不超过50）
输出格式
输出所有复合词，每行一个。 如果没有复合词，不输出任何内容。
样例输入1
5
cat
car
dog
catcar
cardog
样例输出1
catcar
cardog
样例1说明：
- "catcar"可以拆分成"cat"和"car"，两个都在词典中
- "cardog"可以拆分成"car"和"dog"，两个都在词典中
- "cat"、"car"、"dog"本身不能拆分（长度太短）
样例输入2
4
a
b
ab
ba
样例输出2
ab
ba
样例2说明：
- "ab" = "a" + "b"，两个都在词典中
- "ba" = "b" + "a"，两个都在词典中
样例输入3
3
hello
world
test
样例输出3
（无输出）
样例3说明：
- 没有单词可以拆分成两个在词典中的单词
提示
- 先将所有单词插入Trie树
- 对于每个单词，枚举所有可能的断点位置（从1到length-1）
- 对于每个断点，检查左右两部分是否都在Trie树中
- 使用
substr(0, i)获取左子串，substr(i)获取右子串 - 时间复杂度：O(ns²)，其中s是字符串平均长度
考察知识点总结
- ✅ Trie字典树的插入和查询
- ✅ 字符串分割（substr函数）
- ✅ 枚举算法（枚举断点）
- ✅ 复合条件判断
难度评估
难度： ⭐⭐⭐⭐☆（中高）
适合： 学习Trie字典树的应用和枚举算法