例如,如果输入字符串是 helloworld,我希望输出如下:
do
he
we
low
hell
hold
roll
well
word
hello
lower
world
...
一直到最长的单词,即 helloworld 子字符串的字谜。例如在 Scrabble 中。输入字符串可以是任意长度,但很少超过 16 个字符。
我已经进行了搜索并提出了类似 trie 的结构,但我仍然不确定如何实际执行此操作。
用于保存有效条目字典的结构将对效率产生巨大影响。将其组织为一棵树,根是单数零字母“单词”,即空字符串。root 的每个子节点是可能单词的单个第一个字母,这些子节点是可能单词的第二个字母,依此类推,每个节点都标记为它是否实际上构成了一个单词。
您的测试器函数将是递归的。它以零个字母开头,从有效条目树中找到“”不是一个单词但它确实有孩子,所以你递归地调用你的测试器,你的起始词(没有字母)附加你的每个可用的剩余字母输入字符串(当时所有的字符串)。检查树中的每个单字母条目,如果有效,请记下;如果是孩子,则重新调用附加每个剩余可用字母的测试器函数,依此类推。
例如,如果您的输入字符串是“helloworld”,您将首先使用“”调用递归测试器函数,将剩余的可用字母“helloworld”作为第二个参数传递。函数看到“”不是单词,但子“h”确实存在。所以它用“h”和“elloworld”来称呼自己。函数看到“h”不是一个词,但存在子“e”。所以它用“he”和“lloworld”来称呼自己。函数看到标记了“e”,所以“he”是一个单词,注意。此外,子“l”存在,因此下一个调用是“hel”和“loworld”。它接下来会找到“hell”,然后是“hello”,然后必须退出,然后可能会找到“hollow”,
我无法抗拒我自己的实现。它通过按字母顺序对所有字母进行排序,并将它们映射到可以从中创建的单词来创建字典。这是一个 O(n) 启动操作,无需查找所有排列。您可以将字典实现为另一种语言的 trie,以实现更快的加速。
“getAnagrams”命令也是一个 O(n) 操作,它在字典中搜索每个单词以查看它是否是搜索的子集。在我的笔记本电脑上执行 getAnagrams("radiotelegraphically")"(一个 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']
您想要的数据结构称为有向无环词图 (dawg),Andrew Appel 和 Guy Jacobsen 在他们的论文“世界上最快的拼字游戏”中对其进行了描述,不幸的是他们选择不在线免费提供。ACM 会员或大学图书馆将为您提供。
我已经用至少两种语言实现了这个数据结构——它简单、易于实现,而且非常非常快。
一种简单的方法是生成所有“子字符串”,并为每个“子字符串”检查它是否是一组可接受单词的元素。例如,在 Python 2.6 中:
import itertools
import urllib
def words():
f = urllib.urlopen(
'http://www.cs.umd.edu/class/fall2008/cmsc433/p5/Usr.Dict.Words.txt')
allwords = set(w[:-1] for w in f)
f.close()
return allwords
def substrings(s):
for i in range(2, len(s)+1):
for p in itertools.permutations(s, i):
yield ''.join(p)
def main():
w = words()
print '%d words' % len(w)
ss = set(substrings('weep'))
print '%d substrings' % len(ss)
good = ss & w
print '%d good ones' % len(good)
sgood = sorted(good, key=lambda w:(len(w), w))
for aword in sgood:
print aword
main()
将发出:
38617 words
31 substrings
5 good ones
we
ewe
pew
wee
weep
当然,正如其他回复所指出的那样,有目的地组织数据可以大大加快运行时间——尽管快速字谜查找器的最佳数据组织可能会有所不同……但这在很大程度上取决于字典的性质允许的字数(几万,比如这里 - 还是数百万?)。应该考虑哈希映射和“签名”(基于对每个单词中的字母进行排序),以及尝试 &c。
你想要的是一个power set的实现。
也看看 Eric Lipparts 的博客,他不久前在博客上写过这件事
编辑:
这是我编写的从给定字符串中获取 powerset 的实现...
private IEnumerable<string> GetPowerSet(string letters)
{
char[] letterArray = letters.ToCharArray();
for (int i = 0; i < Math.Pow(2.0, letterArray.Length); i++)
{
StringBuilder sb = new StringBuilder();
for (int j = 0; j < letterArray.Length; j++)
{
int pos = Convert.ToInt32(Math.Pow(2.0, j));
if ((pos & i) == pos)
{
sb.Append(letterArray[j]);
}
}
yield return new string(sb.ToString().ToCharArray().OrderBy(c => c).ToArray());
}
}
此函数为我提供了构成传入字符串的字符的幂集,然后我可以将它们用作变位词字典的键...
Dictionary<string,IEnumerable<string>>
我像这样创建了我的字谜词典......(可能有更有效的方法,但这很简单,而且对于拼字游戏单词列表来说足够快)
wordlist = (from s in fileText.Split(new string[] { Environment.NewLine }, StringSplitOptions.RemoveEmptyEntries)
let k = new string(s.ToCharArray().OrderBy(c => c).ToArray())
group s by k).ToDictionary(o => o.Key, sl => sl.Select(a => a));
我相信这个问题的答案中的 Ruby 代码也能解决你的问题。
像Tim J一样,Eric Lippert的博客文章首先出现在我的脑海中。我想补充一点,他写了一篇关于如何提高他第一次尝试的表现的后续文章。
我最近在手机上玩了很多 Wordfeud,我很好奇我是否可以想出一些代码来给我一个可能的单词列表。以下代码采用您的可用源字母(* 表示通配符)和一个包含允许单词(TWL、SOWPODS 等)主列表的数组,并生成一个匹配列表。它通过尝试从源字母构建主列表中的每个单词来做到这一点。
写完代码就找到了这个话题,肯定没有John Pirie的方法或者DAWG算法那么高效,但是还是挺快的。
public IList<string> Matches(string sourceLetters, string [] wordList)
{
sourceLetters = sourceLetters.ToUpper();
IList<string> matches = new List<string>();
foreach (string word in wordList)
{
if (WordCanBeBuiltFromSourceLetters(word, sourceLetters))
matches.Add(word);
}
return matches;
}
public bool WordCanBeBuiltFromSourceLetters(string targetWord, string sourceLetters)
{
string builtWord = "";
foreach (char letter in targetWord)
{
int pos = sourceLetters.IndexOf(letter);
if (pos >= 0)
{
builtWord += letter;
sourceLetters = sourceLetters.Remove(pos, 1);
continue;
}
// check for wildcard
pos = sourceLetters.IndexOf("*");
if (pos >= 0)
{
builtWord += letter;
sourceLetters = sourceLetters.Remove(pos, 1);
}
}
return string.Equals(builtWord, targetWord);
}