查找是否可以从字符矩阵中获得字符串

Question

o f a s
l l q w
z o w k 

我能想到的唯一方法是一个回溯算法，它搜索这个词是否可能。有没有其他更快的算法来解决这个问题？

假设我有很多查询（关于查找一个单词是否存在）。那么是否可以做一些预处理来更快地回答查询呢？

Answer 1

您可以使用DFS解决这个问题。让我们为这个问题定义一个图。图的顶点将由矩阵的单元和我们正在搜索的字符串的前缀长度的组合的单元组成。当我们在一个给定的顶点，这将意味着指定前缀的所有字符都匹配到目前为止，我们目前在给定的单元格。

我们将边定义为连接与边相邻的单元格并执行“有效”事务。也就是说，我们要搜索的单元格应该是我们正在搜索的字符串中的下一个单元格。

为了解决这个问题，我们对所有包含字符串的第一个字母和前缀长度1（意味着我们匹配了第一个字母）的单元格进行DFS。从那以后，我们继续搜索，在每一步中，我们计算哪些是离开当前位置的边（单元格/字符串前缀长度组合）。第一次到达长度为L-字符串长度的前缀时终止。