algorithm - 解决填字游戏的算法

我刚刚通过这个问题，除了 bruteforce 给定一个二维字符数组和一个有效单词的原始列表之外，我想不出任何更好的方法。
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....

最佳答案

确保您有一个按字母顺序排序的有效单词列表。你可以在 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)。

祝你好运。

关于algorithm - 解决填字游戏的算法，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/14704546/