问解决纵横字谜的算法

EN

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

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

使用一组有效单词来验证字母序列是否为有效单词(在固定时间内)。

现在为每个startposition调用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 )时间内找到答案，其中字符数组的x和y维度，以及有效单词列表的大小w。这并不比最坏的情况更好(考虑到lg w验证)，但在我看来这是不可能的。这样，预期的运行时会更好。

如果有效单词的列表很小，您还可以为正确单词的所有有效开头构建一个集合。在这种情况下，您可以在固定时间内验证您是否正在查找正确的单词，最坏的情况将减少到O(x^2 * y^2)。

祝好运。

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

您还可以对数组的已处理路径和单词部分的类似输入使用memoization

记忆示例：

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]
 }

我没有添加任何结束情况，例如边框，它很容易添加。我的意图是给你一个大概的概念。

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

第一步是对有效单词字典进行预处理，并将它们放入trie中。这使您可以有效地回答如下问题：

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

你可以使用trie在O(lenght of the prefix) time中回答这个问题。

然后假设你已经选择了一个单词的开始方块。您现在需要在4个方向上遍历网格，并检查到目前为止获得的前缀是否是有效的前缀。如果不是，那么您将不会在此方向上进一步遍历。另一方面，如果前缀到目前为止是一个有效的单词，您可以只打印它。遍历可以使用DFS或BFS来完成(实际上并不重要)。重要的部分是使用trie快速检查有效的前缀和有效的单词。