列出以<用户输入>开头的所有词汇

Question

我想知道怎么写一个程序，让用户输入一个字符串，然后程序生成一个以这个字符串开头的单词列表。

比如：
用户输入：“abd”
程序输出：abdicate（放弃），abdomen（腹部），abduct（绑架）……

谢谢！

---

补充：我在用Python，不过我觉得这个问题跟编程语言没太大关系。

Answer 1

实现这个目标的一个好方法是使用有向图来存储你的字典。虽然一开始需要花点时间来设置，但一旦完成，之后进行你想要的搜索就会变得相对简单。

图中的每个节点代表你单词中的一个字母，因此每个节点会有一个进入的链接和最多26个（在英语中）出去的链接。

你还可以采用一种混合的方法，保持一个包含你字典的排序列表，同时使用有向图作为字典的索引。这样，你只需在有向图中查找你的前缀，然后到字典中的那个位置去，找出所有符合你搜索条件的单词。

Answer 2

使用一种叫做字典树的数据结构。

把你的单词列表放到字典树里。从树的根节点到叶子节点的每一条路径都是一个有效的单词。而从根节点到某个中间节点的路径则代表一个前缀，这个中间节点的子节点就是这个前缀的有效补全。

Answer 3

如果你在一个类似Debian的机器上，

#!/bin/bash
echo -n "Enter a word: "
read input
grep "^$input" /usr/share/dict/words

在我的P200上，这个过程只花了0.040秒。