algorithm - 在矩阵中查找有效单词

Question

给定一个单词字典，两个 APIIs_word(字符串)Is_prefix(字符串)和一个 NxN 矩阵，每个位置由一个字符组成。如果从任何位置 (i,j) 你可以移动在四个方向中的任意一个方向，找出矩阵中所有可以组成的有效词。(不允许循环，即如果你从(i，j)开始并移动到(i-1，j)然后形成一个单词位置从这个位置你不能回到 (i,j))

我的尝试::我可以看到一个指数解决方案，我们遍历所有可能性并跟踪已访问的索引。我们能有更好的解决方案吗？

Answer 1

这是我能做的最好的了:

1. 在允许的一半方向上枚举所有可能的字符串。 (您可以反转字符串以获得其他方向。)
2. 对于每个字符串中的每个起始字符位置，构建子字符串，直到它们既不是单词也不是前缀。

编辑:我可能误解了这个问题。我认为每个单独的单词只能由同一个方向的移动组成。