algorithm - 在矩阵中查找有效词

Question

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

我尝试了什么 :: 我可以看到一个指数解决方案，我们通过所有可能性和跟踪已经访问过的索引。我们能有更好的解决方案吗？

Answer 1

这是我能做的最好的：

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

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

Answer 2

我倾向于通过创建两个并行数据结构来解决这个问题。一个是单词列表（删除重复项）。另一个是前缀矩阵，其中每个元素都是一个列表。希望可以使用这样的数据结构。列表矩阵实际上可以是一个三元组列表，单词和坐标在原始矩阵中。

在任何情况下，遍历原始矩阵并在每个元素上调用 isword()。如果是单词，则将该单词插入单词列表。

然后遍历原始矩阵，并比较每个元素上的调用 isprefix()。如果是前缀，则插入前缀矩阵。

然后，通过前缀矩阵并测试前缀与附加字母的四种组合。如果是单词，则放入单词列表。如果是前缀，则添加到前缀矩阵，在最后一个字母的位置。记住两者都要，因为一个词可以是前缀。

此外，在前缀列表中，您不仅需要保留字母列表，还需要保留已使用字母的位置。这用于防止循环。

然后继续这个过程，直到没有单词和前缀。

很难衡量这种结构的复杂性，因为它似乎取决于字典的内容。

Answer 3

我认为你不能在这里击败指数。证明？

考虑一下当你有一个矩阵的情况，你有一个字母排列，这样每个组合都是一个有效的字典单词，即当你从 [i,j] 开始时，例如 [i,j] 与 [i-1,j ] 或 [i+1,j] 或 [i,j+1] 或 [i,j-1] 都是 2 个字母的单词，并且递归地继续，即长度 n（根据您的规则）的任何组合都是一个单词。在这种情况下，你不能比蛮力做得更好。