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
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?
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.
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.
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.