如何编写一个程序，让用户输入一个字符串，然后该程序生成以该字符串开头的单词列表？

前任：
用户：" abd"
程序：退位，收腹，绑架...

谢谢！

编辑：我正在使用python，但我认为这是一个与语言无关的问题。

解决方案

var words = from word in dictionary
            where word.key.StartsWith("bla-bla-bla");
            select word;

尝试使用正则表达式搜索单词列表，例如/ ^ word /并报告所有匹配项。

def main(script, name):
    for word in open("/usr/share/dict/words"):
        if word.startswith(name):
            print word,

if __name__ == "__main__":
    import sys
    main(*sys.argv)

最好的方法之一是使用有向图来存储字典。它需要一点点设置，但是一旦完成，就可以轻松进行我们正在谈论的搜索类型。

图中的节点与我们单词中的字母相对应，因此每个节点将具有一个传入链接和最多26个(英语)传出链接。

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

使用特里。

将单词列表添加到特里。从根到叶子的每条路径都是有效的单词。从根到中间节点的路径表示前缀，并且中间节点的子级是该前缀的有效补全。

如果我们真的想提高效率，请使用后缀树或者后缀数组Wikipedia文章。

问题是设计了哪些后缀树。
这里甚至有Python的实现

如果我们需要非常快，请使用一棵树：

构建一个数组，并根据第一个字母将单词分成26组，然后根据第二个字母将每个条目分为26个，然后再次。

因此，如果用户键入" abd"，则将查找Array [0] [1] [3]并获取所有以此开头的单词的列表。那时，列表应该足够小，可以传递给客户端并使用javascript进行过滤。

如果我们使用的是debian [-like]机器，

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

占用我的P200的所有0.040秒。

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]

如果我们确实想要速度，请使用特里/自动机。但是，考虑到单词列表已排序，这将比简单地扫描整个列表更快。

from itertools import takewhile, islice
import bisect

def prefixes(words, pfx):
    return list(
             takewhile(lambda x: x.startswith(pfx), 
                       islice(words, 
                              bisect.bisect_right(words, pfx), 
                              len(words)))

请注意，就字典的大小而言，自动机为O(1)，而对于实际上以前缀开头的字符串数，此算法为O(log(m))，然后为O(n)。完整扫描为O(m)，其中n << m。

如果词典确实很大，我建议使用python文本索引进行索引(PyLucene注意，我从未使用过lucene的python扩展名)。搜索将非常有效，甚至可以返回搜索"分数"。

另外，如果字典是相对静态的，那么我们甚至没有经常重新索引的开销。

不要使用火箭筒杀死苍蝇。使用像SQLite一样简单的方法。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。我们需要每种现代语言都具备的所有工具，我们可以这样做：

"SELECT word FROM dict WHERE word LIKE "user_entry%"

闪电般快，婴儿可以做到。此外，它具有便携性，持久性和易于维护性。

Python Tuto：

http://www.initd.org/pub/software/pysqlite/doc/usage-guide.html

线性扫描速度很慢，但是前缀树可能会过大。保持单词排序并使用二进制搜索是一种快速而简单的折衷方案。

import bisect
words = sorted(map(str.strip, open('/usr/share/dict/words')))
def lookup(prefix):
    return words[bisect.bisect_left(words, prefix):bisect.bisect_right(words, prefix+'~')]

>>> lookup('abdicat')
['abdicate', 'abdication', 'abdicative', 'abdicator']

大多数Pythonic解决方案

# set your list of words, whatever the source
words_list = ('cat', 'dog', 'banana')
# get the word from the user inpuit
user_word = raw_input("Enter a word:\n")
# create an generator, so your output is flexible and store almost nothing in memory
word_generator = (word for word in words_list if word.startswith(user_word))

# now you in, you can make anything you want with it 
# here we just list it :

for word in word_generator :
    print word

请记住，生成器只能使用一次，因此将其转到一个列表(使用list(word_generator))，或者如果希望多次使用，请使用itertools.tee函数。

最好的方法：

将其存储到数据库中，然后使用SQL查找所需的单词。如果词典中有很多单词，它将更快，更高效。

Python提供了数千种DB API来完成工作；-)