3

我刚刚解决了这个问题，我想不出比暴力破解更好的方法给定一个二维字符数组和一个有效单词的原始列表。1）从数组中找到所有有效的单词。从数组中的每个元素，您可以向上、向下、向右或向左遍历。例如，

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

上述二维数组中的有效单词 -> god, goat, godbody, amour,....

4

3 回答 3

1

您应该将此列表预处理为前缀树，而不是在前缀树上的二维数组中使用蛮力搜索。

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

记忆示例：

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

我没有添加任何结束案例，例如边框，很容易添加。我的目的是给你一个大致的想法。

于 2013-02-05T10:02:41.137 回答
1

确保您有一个按字母顺序排列的有效单词列表。您可以在 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 w) 时间内找到答案，其中 char 数组的 x 和 y 维度以及有效单词列表的大小。这并不比最坏的情况好（鉴于 lg w 验证），但这对我来说似乎是不可能的。这样，预期的运行时间会更好。

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

祝你好运。

于 2013-02-05T10:20:16.867 回答
0

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

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

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

O(lenght of the prefix)您可以使用 trie 及时回答这个问题。

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

于 2013-02-05T10:05:39.533 回答