algorithm - 算法解决纵横字谜

Question

我刚刚解决了这个问题，我想不出比暴力破解更好的方法给定一个二维字符数组和一个有效单词的原始列表。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,....

Answer 1

确保您有一个按字母顺序排序的有效单词列表。您可以在 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 维度为 char 数组，w 为有效单词列表的大小。这并不比最坏的情况好(考虑到 lg w 验证)，但这对我来说似乎是不可能的。这样预期的运行时间会更好。

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

祝你好运。