algorithm - 4x4 二维字符矩阵排列

Question

我有一个像这样的 4x4 二维字符数组:

A B C D
U A L E
T S U G
N E Y I

现在，我需要找到 3 个字符、4 个字符等的所有排列，直到 10。

因此，可以从中“找到”的一些词是 TEN、BALD、BLUE、GUYS.

我确实为此搜索过 SO 并用 Google 搜索过，但没有具体的帮助。你能把我推向我应该学习算法的正确方向吗(也许是 A*？)。请保持温和，因为我不是算法专家(不是我们所有人(好吧，至少是大多数 :))，但我愿意学习只是不知道从哪里开始。

Answer 1

啊哈，这就是 Boggle 游戏，不是吗...您不需要排列，您需要一个图表，并且您想在图表中找到单词。

好吧，我会先将字符安排为图形节点，然后将它们连接到它们的直接邻居和对角线邻居。

现在您只想搜索图表。对于 16 个起始节点中的每一个，您都将执行递归。当您移动到一个新节点时，您必须将其标记为正在使用，这样您就不能再次移动到它。当你离开一个节点(已经完全搜索它)时，你取消标记它。

我希望你明白这是怎么回事......

对于每个节点，您将访问它的每个邻居并将该字符添加到一个字符串中。如果您在构建字典时考虑了这种搜索，您将立即能够看到您目前拥有的字符是否是单词的开头。这很好地缩小了搜索范围。

我所说的字典类型是一棵树，其节点对应字母表中的每个字母都有一个子节点。这些的美妙之处在于您只需要存储您当前在搜索中到达的树节点。如果您确定找到了一个词，您只需通过父节点回溯以找出它是哪个词。

使用这种树形样式和深度优先图形搜索，您可以同时搜索所有可能的单词长度。这是我能想到的最有效的方法。

---

让我为您的图形搜索编写一个伪代码函数:

function FindWords( graphNode, dictNode, wordsList )
    # can't use a letter twice
    if graphNode.used then return

    # don't continue if the letter not part of any word
    if not dictNode.hasChild(graphNode.letter) then return
    nextDictNode = dictNode.getChild(graphNode.letter)

    # if this dictionary node is flagged as a word, add it to our list
    nextDictNode.isWord()
        wordsList.addWord( nextDictNode .getWord() )
    end

    # Now do a recursion on all our neighbours
    graphNode.used = true
    foreach nextGraphNode in graphNode.neighbours do
        FindWords( nextGraphNode, nextDictNode, wordsList )
    end
    graphNode.used = false
end

当然，要开始整个事情:

foreach graphNode in graph do
    FindWords( graphNode, dictionary, wordsList )
end

剩下的就是构建图形和字典。我只记得那个字典数据结构叫什么!这是一个Trie .如果你需要更节省空间的存储，你可以压缩成一个 Radix Tree或类似的，但到目前为止最简单(也是最快)的是直接使用 Trie。