12

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

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

一直到最长的单词,即 helloworld 子字符串的字谜。例如在 Scrabble 中。输入字符串可以是任意长度,但很少超过 16 个字符。

我已经进行了搜索并提出了类似 trie 的结构,但我仍然不确定如何实际执行此操作。

4

8 回答 8

14

用于保存有效条目字典的结构将对效率产生巨大影响。将其组织为一棵树,根是单数零字母“单词”,即空字符串。root 的每个子节点是可能单词的单个第一个字母,这些子节点是可能单词的第二个字母,依此类推,每个节点都标记为它是否实际上构成了一个单词。

您的测试器函数将是递归的。它以零个字母开头,从有效条目树中找到“”不是一个单词但它确实有孩子,所以你递归地调用你的测试器,你的起始词(没有字母)附加你的每个可用的剩余字母输入字符串(当时所有的字符串)。检查树中的每个单字母条目,如果有效,请记下;如果是孩子,则重新调用附加每个剩余可用字母的测试器函数,依此类推。

例如,如果您的输入字符串是“helloworld”,您将首先使用“”调用递归测试器函数,将剩余的可用字母“helloworld”作为第二个参数传递。函数看到“”不是单词,但子“h”确实存在。所以它用“h”和“elloworld”来称呼自己。函数看到“h”不是一个词,但存在子“e”。所以它用“he”和“lloworld”来称呼自己。函数看到标记了“e”,所以“he”是一个单词,注意。此外,子“l”存在,因此下一个调用是“hel”和“loworld”。它接下来会找到“hell”,然后是“hello”,然后必须退出,然后可能会找到“hollow”,

于 2009-05-19T01:38:29.593 回答
9

我无法抗拒我自己的实现。它通过按字母顺序对所有字母进行排序,并将它们映射到可以从中创建的单词来创建字典。这是一个 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']
于 2009-05-19T07:13:19.577 回答
6

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

我已经用至少两种语言实现了这个数据结构——它简单、易于实现,而且非常非常快。

于 2009-05-19T02:25:49.997 回答
2

一种简单的方法是生成所有“子字符串”,并为每个“子字符串”检查它是否是一组可接受单词的元素。例如,在 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。

于 2009-05-19T01:50:24.780 回答
2

你想要的是一个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));
于 2009-05-19T01:26:39.697 回答
0

我相信这个问题的答案中的 Ruby 代码也能解决你的问题。

于 2009-05-19T03:28:27.407 回答
0

Tim J一样,Eric Lippert的博客文章首先出现在我的脑海中。我想补充一点,他写了一篇关于如何提高他第一次尝试的表现的后续文章。

于 2009-05-19T01:41:42.787 回答
0

我最近在手机上玩了很多 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);

}
于 2011-01-26T21:25:43.790 回答