列出以<user input>开头的字典中的所有单词

Question

如何制作一个用户输入字符串的程序,程序会生成一个以该字符串开头的单词列表？

例:
用户:"abd"
计划:abdicate,abdomen,abduct ......

谢谢!

---

编辑:我正在使用python,但我认为这是一个相当语言无关的问题.

Answer 1

使用特里.

将您的单词列表添加到trie.从根到叶子的每条路径都是有效的单词.从根节点到中间节点的路径表示前缀,中间节点的子节点是前缀的有效完成.

Answer 2

执行此操作的最佳方法之一是使用有向图来存储字典.它需要一些设置,但一旦完成,那么你正在谈论的搜索类型相当容易.

图中的节点对应于单词中的字母,因此每个节点将具有一个传入链接和最多26个(英语)传出链接.

您还可以使用混合方法,在该方法中维护包含字典的排序列表,并使用有向图作为字典的索引.然后,您只需在有向图中查找前缀,然后转到词典中的该点并吐出符合搜索条件的所有单词.

Answer 3

如果你在debian [-like]机器上,

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

在我的P200上占用0.040全部.

Answer 4

egrep `read input && echo ^$input` /usr/share/dict/words

哦，我没有看到Python编辑，这里是Python中的同样的东西

my_input = raw_input("Enter beginning of word: ")
my_words = open("/usr/share/dict/words").readlines()
my_found_words = [x for x in my_words if x[0:len(my_input)] == my_input]