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

Question

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

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

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

我还有一个字典单词数组。

如果字符数组可以组合成字典中的一个单词，那么最好/最快的查找方法是什么？例如，上面的数组可以使单词：

“拍拍”，“老鼠”，“在”，“到”，“奔跑”(哈哈)

但不是"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

EDIT:我做了两个改变，使它变得更快:将单词存储在trie的每个末端节点，这样它就不需要重新构建。并将输入字母存储为哈希集的数组，而不是数组的数组，从而可以快速调用Contains()。

Answer 2

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

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

也许您可以使用前缀树(a trie)、某种智能哈希表或类似的东西。

无论如何，你可能不得不尝试所有的可能性，并对照字典检查它们。也就是说，如果你有三个数组，每个数组有三个值，那么就会有3^3+3^2+3^1=39组合需要检查。如果这个过程太慢，那么也许你可以在字典前面粘贴一个Bloom filter，来快速检查一个单词是否确实不在字典中。

编辑:不管怎样，这不是和拼字游戏本质上是一样的吗？也许试着在谷歌上搜索"scrabble algorithm“会给你一些好的线索。

Answer 3

重构后的问题可以通过生成和测试来回答。因为您有4个字母和10个数组，所以只有大约100万个可能的组合(如果您允许一个空字符，则有1000万个)。您需要一种有效的方法来查找它们，使用BDB或某种基于磁盘的散列。

之前发布的trie解决方案也应该可以工作，只是在搜索的每个步骤中可以选择的字符对你有更多的限制。它也应该更快。