用于解决填字游戏的算法

Question

我刚刚看到这个问题，除了暴力搜索，我想不到更好的方法。题目描述如下：给定一个二维字符数组和一个有效单词列表。 1）在数组中找出所有有效单词。从数组中的每个元素开始，你可以向上、向下、向右或向左遍历。 例如：

g o d b o d y
t a m o p r n 
u i r u s m p

上述2D数组中的有效单词->god，goat，godbody，amour等。

- kamal

---

你有一个存储有效单词的列表吗？你有多少个这样不同的单词？你能预处理这个列表吗？ - Michael

你有一个常量的二维数组还是它会改变？你有一个常量有效单词列表还是它会改变？ - Michael

我有一个包含有效单词的字典，而二维数组将保持不变。 - kamal

你的例子中GOAT出现在哪里？DOE（从后往前读是EOD）是否也合格？ - vonbrand

Answer 1

你应该将此列表预处理为前缀树，然后在前缀树上使用暴力搜索2D数组。

您还可以对数组的已处理路径和单词部分的类似输入使用备忘录技术。

备忘录示例：

RecursiveMatch(i,j,wordPart)

 if ((i,j,wordPart) in cache) 
   print cache[i,j,wordPart]
   return;
 if a[i,j] on the prefixTreePath){
   cache[i,j,wordPart]+=RecursiveMatch(i+1,j,wordPart[1:])
   cache[i,j,wordPart]+=RecursiveMatch(i-1,j,wordPart[1:])
   cache[i,j,wordPart]+=RecursiveMatch(i,j+1,wordPart[1:])
   cache[i,j,wordPart]+=RecursiveMatch(i,j-1,wordPart[1:])
   print cache[i,j,wordPart]
 }

我还没有添加任何结束情况，例如边框，这很容易添加。 我的意图是给你一个大致的想法。

- Michael

Answer 2

请确保您有一个按字母顺序排序的有效单词列表。您可以在n lg n时间内构建此列表。

现在，您拥有了这个排序后的列表，您可以在lg n时间内验证一个字符序列是否是正确单词的开头。

使用一组有效单词来验证一个字母序列是否是有效单词（在常数时间内）。

现在对于每个起始位置调用getWords（input，startX，startY，new ArrayList（），“”），并合并结果列表：

public List<String> getWords(char[][] input, int x, int y, List<String> result, String current){
    if(isValidWord(current))
         result.add(current);

    if(isValidStartOfWord(current)){
         // call getWords recursively for all valid directions, concatenating the char to current
    }

    return result;
 }

这样，您将在O(x^2 * y^2 * lg w)时间内找到答案，其中x和y是字符数组的维度，w是有效单词列表的大小。虽然不如最坏情况（考虑到lg w验证），但我认为这似乎不可能。预期运行时间以此方式更好。

如果有效单词列表很小，您还可以建立一个集合，包含所有正确单词的有效开头。在这种情况下，您可以在常数时间内验证是否正在正确的单词路径上，最坏情况降至O(x^2 * y^2)。

祝你好运。

- Jos

Answer 3

一种算法依赖于一种称为前缀树或树的合适数据结构。

第一步是预处理您的有效单词字典并将它们放入trie中。 这使您能够高效地回答这样的问题：

给定的前缀是否是有效前缀？

使用trie，您可以在O(前缀长度)时间内回答此问题。

然后假设您已选择了一个单词的起始方块。现在需要沿着4个方向遍历网格，并检查迄今为止获得的前缀是否是有效前缀。如果不是，则不会在此方向上进一步遍历。另一方面，如果到目前为止的前缀是有效单词，则可以直接打印出来。 遍历可以使用DFS或BFS进行（实际上并不重要）。 重要的是要使用trie快速检查有效前缀和有效单词。

- Petar Ivanov

---

你不觉得将字典中所有有效的单词放入 Trie 中会占用很多空间吗？ - kamal

@kamal：它将比你的字典占用更少的空间。在复杂性方面至关重要。 - Michael