获取所有子串(拼字游戏)字符串的所有单词列表的算法？

Question

例如,如果输入字符串是helloworld,我希望输出如下:

do
he
we
low
hell
hold
roll
well
word
hello
lower
world
...

一直到最长的单词,这是一个helloworld子字符串的字谜.就像Scrabble一样.输入字符串可以是任意长度,但很少超过16个字符.

我已经完成了搜索并想出了像trie这样的结构,但我仍然不确定如何实际执行此操作.

Answer 1

用于保存有效条目字典的结构将对效率产生巨大影响.将它组织为树,root是单个零字母"word",空字符串.root的每个子节点是可能单词的单个首字母,可能单词的第二个字母等,其中每个节点标记为是否实际形成单词.

您的测试人员功能将是递归的.它以零字母开头,从有效条目的树中找到""不是一个单词,但它确实有子项,所以你用你的起始单词(没有字母)递归地调用你的测试者,你的每一个可用的剩余字母都是输入字符串(在那一点上都是它们).如果有效,请检查树中的每个单字母条目; 如果孩子,重新调用测试器功能附加每个剩余的可用字母,等等.

因此,例如,如果您的输入字符串是"helloworld",那么您将首先使用""调用递归测试器函数,并将剩余的可用字母"helloworld"作为第二个参数传递.函数看到""不是单词,但是孩子"h"确实存在.所以它称自己为"h"和"elloworld".功能看到"h"不是单词,但是孩子"e"存在.所以它称自己为"他"和"lloworld".函数看到"e"被标记,所以"他"是一个单词,请注意.此外,孩子"l"存在,所以下一个呼叫是"hel"与"loworld".它接下来会发现"地狱",然后是"你好",然后将不得不退出并可能接下来找到"空心",然后再一次支持空字符串然后以"e"字开头.

Answer 2

我无法抗拒自己的实施.它通过按字母顺序对所有字母进行排序,并将它们映射到可以从中创建的单词来创建字典.这是一个O(n)启动操作,无需查找所有排列.您可以将字典实现为另一种语言的trie,以获得更快的加速.

"getAnagrams"命令也是一个O(n)操作,它搜索字典中的每个单词以查看它是否是搜索的子集.做getAnagrams("无线电报")"(一个20个字母的单词)在我的笔记本电脑上花了大约1秒钟,并返回了1496个字谜.

# Using the 38617 word dictionary at 
# http://www.cs.umd.edu/class/fall2008/cmsc433/p5/Usr.Dict.Words.txt
# Usage: getAnagrams("helloworld")

def containsLetters(subword, word):
    wordlen = len(word)
    subwordlen = len(subword)

    if subwordlen > wordlen:
        return False

    word = list(word)
    for c in subword:
        try:
            index = word.index(c)
        except ValueError:
            return False
        word.pop(index)
    return True

def getAnagrams(word):
    output = []
    for key in mydict.iterkeys():
        if containsLetters(key, word):
            output.extend(mydict[key])

    output.sort(key=len)
    return output

f = open("dict.txt")
wordlist = f.readlines()
f.close()

mydict = {}
for word in wordlist:
    word = word.rstrip()
    temp = list(word)
    temp.sort()
    letters = ''.join(temp)

    if letters in mydict:
        mydict[letters].append(word)
    else:
        mydict[letters] = [word]

示例运行:

>>> getAnagrams("helloworld")
>>> ['do', 'he', 'we', 're', 'oh', 'or', 'row', 'hew', 'her', 'hoe', 'woo', 'red', 'dew', 'led', 'doe', 'ode', 'low', 'owl', 'rod', 'old', 'how', 'who', 'rho', 'ore', 'roe', 'owe', 'woe', 'hero', 'wood', 'door', 'odor', 'hold', 'well', 'owed', 'dell', 'dole', 'lewd', 'weld', 'doer', 'redo', 'rode', 'howl', 'hole', 'hell', 'drew', 'word', 'roll', 'wore', 'wool','herd', 'held', 'lore', 'role', 'lord', 'doll', 'hood', 'whore', 'rowed', 'wooed', 'whorl', 'world', 'older', 'dowel', 'horde', 'droll', 'drool', 'dwell', 'holed', 'lower', 'hello', 'wooer', 'rodeo', 'whole', 'hollow', 'howler', 'rolled', 'howled', 'holder', 'hollowed']

Answer 3

您想要的数据结构称为定向非循环字图(dawg),Andrew Appel和Guy Jacobsen在他们的论文"世界上最快的拼字游戏程序"中对其进行了描述,不幸的是他们选择不在网上免费提供.ACM会员或大学图书馆将为您提供.

我已经用至少两种语言实现了这种数据结构 - 它简单,易于实现,而且速度非常快.