给定字符矩阵和字符串矩阵，请确定是否可以从矩阵中获取字符串。从矩阵中的每个字符，我们可以向上/向下/向右/向左移动。例如，如果矩阵[3] [4]为：
o f a s
l l q w
z o w k
且字符串为follow，则函数应返回true。
我能想到的唯一方法是回溯算法，该算法搜索单词是否可能。还有其他更快的算法可以解决此问题吗？
并假设我有很多查询（查找是否存在一个单词）。然后可以做一些预处理以更快地回答查询吗？
您可以使用DFS解决此问题。让我们为问题定义一个图形。图的顶点将包含矩阵的单元格和我们要搜索的字符串的前缀长度的组合的单元格。当我们位于给定的顶点时，这意味着指定前缀的所有字符到目前为止都已匹配，并且我们当前位于给定的像元处。
我们将边定义为连接边相邻的单元并进行“有效”交易。那就是我们要查找的单元格应该是我们要搜索的字符串中的下一个单元格。
为了解决该问题，我们对所有包含字符串首字母和前缀长度1（意味着我们已经匹配了首字母）的单元进行了DFS。从那里开始，继续搜索，并在每个步骤上计算出当前位置（单元格/字符串前缀长度组合）之外的边。我们第一次到达长度前缀L-字符串的长度时终止。
请注意，DFS可能被认为是回溯，但是更重要的是跟踪我们已经访问过的图中的节点。因此，整体复杂度被结合N * M * L，其中N和M是矩阵的和的尺寸L-该字符串的长度。
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句