如何从字符数组中查找单词？

Question

解决这个问题的最佳方法是什么：

我有一组数组，每个数组中有 3-4 个字符，如下所示：

{p,     {a,    {t,    {m,
 q,      b,     u,     n,
 r,      c      v      o
 s      }      }      }
}

我还有一组字典单词。

查找字符数组是否可以组合形成字典单词之一的最佳/最快方法是什么？例如，上面的数组可以组成单词：

“pat”、“rat”、“at”、“to”、“bum”（笑）
但不是“nub”或“mat”

我应该循环遍历字典来查看是否有单词可以制作或获取字母的所有组合，然后将它们与字典进行比较

Answer 1

我手头上有一些拼字游戏代码，所以我能够将它们组合在一起。我使用的字典是sowpods（267751个单词）。下面的代码将字典读取为文本文件，每行一个大写单词。

代码是 C#：

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.IO;
using System.Diagnostics;

namespace SO_6022848
{
  public struct Letter
  {
    public const string Chars = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
    public static implicit operator Letter(char c)
    {
      return new Letter() { Index = Chars.IndexOf(c) };
    }
    public int Index;
    public char ToChar()
    {
      return Chars[Index];
    }
    public override string ToString()
    {
      return Chars[Index].ToString();
    }
  }

  public class Trie
  {
    public class Node
    {
      public string Word;
      public bool IsTerminal { get { return Word != null; } }
      public Dictionary<Letter, Node> Edges = new Dictionary<Letter, Node>();
    }

    public Node Root = new Node();

    public Trie(string[] words)
    {
      for (int w = 0; w < words.Length; w++)
      {
        var word = words[w];
        var node = Root;
        for (int len = 1; len <= word.Length; len++)
        {
          var letter = word[len - 1];
          Node next;
          if (!node.Edges.TryGetValue(letter, out next))
          {
            next = new Node();
            if (len == word.Length)
            {
              next.Word = word;
            }
            node.Edges.Add(letter, next);
          }
          node = next;
        }
      }
    }

  }

  class Program
  {
    static void GenWords(Trie.Node n, HashSet<Letter>[] sets, int currentArrayIndex, List<string> wordsFound)
    {
      if (currentArrayIndex < sets.Length)
      {
        foreach (var edge in n.Edges)
        {
          if (sets[currentArrayIndex].Contains(edge.Key))
          {
            if (edge.Value.IsTerminal)
            {
              wordsFound.Add(edge.Value.Word);
            }
            GenWords(edge.Value, sets, currentArrayIndex + 1, wordsFound);
          }
        }
      }
    }

    static void Main(string[] args)
    {
      const int minArraySize = 3;
      const int maxArraySize = 4;
      const int setCount = 10;
      const bool generateRandomInput = true;

      var trie = new Trie(File.ReadAllLines("sowpods.txt"));
      var watch = new Stopwatch();
      var trials = 10000;
      var wordCountSum = 0;
      var rand = new Random(37);

      for (int t = 0; t < trials; t++)
      {
        HashSet<Letter>[] sets;
        if (generateRandomInput)
        {
          sets = new HashSet<Letter>[setCount];
          for (int i = 0; i < setCount; i++)
          {
            sets[i] = new HashSet<Letter>();
            var size = minArraySize + rand.Next(maxArraySize - minArraySize + 1);
            while (sets[i].Count < size)
            {
              sets[i].Add(Letter.Chars[rand.Next(Letter.Chars.Length)]);
            }
          }
        }
        else
        {
          sets = new HashSet<Letter>[] { 
          new HashSet<Letter>(new Letter[] { 'P', 'Q', 'R', 'S' }), 
          new HashSet<Letter>(new Letter[] { 'A', 'B', 'C' }), 
          new HashSet<Letter>(new Letter[] { 'T', 'U', 'V' }), 
          new HashSet<Letter>(new Letter[] { 'M', 'N', 'O' }) };
        }

        watch.Start();
        var wordsFound = new List<string>();
        for (int i = 0; i < sets.Length - 1; i++)
        {
          GenWords(trie.Root, sets, i, wordsFound);
        }
        watch.Stop();
        wordCountSum += wordsFound.Count;
        if (!generateRandomInput && t == 0)
        {
          foreach (var word in wordsFound)
          {
            Console.WriteLine(word);
          }
        }
      }
      Console.WriteLine("Elapsed per trial = {0}", new TimeSpan(watch.Elapsed.Ticks / trials));
      Console.WriteLine("Average word count per trial = {0:0.0}", (float)wordCountSum / trials);
    }

  }

}

这是使用测试数据时的输出：

PA
PAT
PAV
QAT
RAT
RATO
RAUN
SAT
SAU
SAV
SCUM
AT
AVO
BUM
BUN
CUM
TO
UM
UN
Elapsed per trial = 00:00:00.0000725
Average word count per trial = 19.0

以及使用随机数据时的输出（不打印每个单词）：

Elapsed per trial = 00:00:00.0002910
Average word count per trial = 62.2

编辑： 我通过两个更改使其速度更快： 存储单词位于特里树的每个终端节点，这样就不必重建它。并将输入字母存储为哈希集数组而不是数组数组，以便 Contains() 调用速度更快。

Answer 2

解决这个问题的方法可能有很多。

您感兴趣的是可用于组成单词的每个字符的数量，以及每个字典单词需要多少个字符。诀窍在于如何有效地在字典中查找这些信息。

也许您可以使用前缀树（trie）、某种智能哈希表或类似的。

不管怎样，你可能必须尝试所有的可能性，并对照字典进行检查。即，如果您有三个数组，每个数组包含三个值，则将有 3^3+3^2+3^1=39 个组合需要检查。如果这个过程太慢，那么也许你可以在字典前面添加一个 Bloom 过滤器，快速检查某个单词是否肯定不在字典中。

编辑： 不管怎样，这不是和 Scrabble 本质上一样吗？也许尝试谷歌搜索“拼字游戏算法”会给你一些很好的线索。

Answer 3

只需通过生成和测试即可回答重新表述的问题。由于您有 4 个字母和 10 个数组，因此您只有大约 100 万种可能的组合（如果允许空白字符，则为 1000 万种）。您需要一种有效的方法来查找它们，使用 BDB 或某种基于磁盘的哈希。

之前发布的 trie 解决方案应该也可以工作，只是您在搜索的每一步中可以选择的字符更多地受到限制。它也应该更快。

Answer 4

我刚刚做了一个非常大的嵌套 for 循环，如下所示：

for(NSString*s1 in [letterList objectAtIndex:0]{
    for(NSString*s2 in [letterList objectAtIndex:1]{
       8 more times...
    }
}

然后我对组合进行二分搜索，看看它是否在字典中，如果在，则将其添加到数组中