查找是否可以从字符矩阵中获得字符串
给出一个由字符和字符串组成的矩阵，确定是否可以从矩阵中获得字符串.从矩阵中的每个字符，我们可以向上/向下/向右/向左移动.例如，如果矩阵[3] [4]为:
Given a matrix of characters and a string, find whether the string can be obtained from the matrix. From each character in the matrix, we can move up/down/right/left. For example, if the matrix[3][4] is:
o f a s
l l q w
z o w k
并且字符串为follow，则该函数应返回true.
and the string is follow, then the function should return true.
我能想到的唯一方法是回溯算法，该算法搜索单词是否可能.还有其他更快的算法可以解决这个问题吗?
The only approach I can think of is a backtracking algorithm that searches whether the word is possible or not. Is there any other faster algorithm to approach this problem?
并假设我有很多查询(查找是否存在一个单词).然后可以做一些预处理以更快地回答查询吗?
And suppose I have a lot of queries (on finding whether a word exists or not). Then can there be some preprocessing done to answer the queries faster?
您可以使用DFS解决此问题.让我们为该问题定义一个图形.图的顶点将包含矩阵的单元格和我们要搜索的字符串的前缀长度的组合的单元格.当我们位于给定的顶点时，这意味着指定前缀的所有字符到目前为止都已匹配，并且我们当前位于给定的像元处.
You can solve this using DFS. Let's define a graph for the problem. The vertices of the graph will comprise of the cell of a combination of cell of the matrix and a length of prefix of the string we are searching for. When we are at a given vertex this will mean that all the characters of the specified prefix were matched so far and that we currently are at the given cell.
我们将边定义为连接边相邻的单元并进行有效"交易.那就是我们要搜索的单元格应该是我们要搜索的字符串中的下一个单元格.
We define edges as connecting cells adjacent by a side and doing a "valid" transaction. That is the cell we are going to should be the next in the string we are searching for.
为解决该问题，我们对所有包含字符串首字母和前缀长度1(意味着我们已经匹配了首字母)的单元进行了DFS.从那里开始，继续搜索，并在每个步骤上计算出当前位置(单元格/字符串前缀长度组合)之外的边.我们在第一次到达长度为L的前缀(字符串的长度)时终止.
To solve the problem we do a DFS from all cells that contain the first letter of the string and prefix length 1(meaning we've matched this first letter). From there on we continue the search and on each step we compute which are the edges going out of the current position(cell/string prefix length combination). We terminate the first time we reach a prefix of length L - the length of the string.
请注意，DFS可能被认为是回溯，但是更重要的是跟踪我们已经访问过的图中的节点.因此，总体复杂度受N * M * L约束，其中N和M是矩阵的维数，而L是字符串的长度.
Note that DFS may be considered backtracking but what is more important is to keep track of the nodes in the graph we've already visited. Thus the overall complexity is bound by N * M * L where N and M are the dimensions of the matrix and L - the length of the string.