Question: How
to implement a function to check whether there is a path for a string in a
matrix of characters? It moves to left,
right, up and down in a matrix, and a cell for a movement. The path can start
from any entry in a matrix. If a cell is occupied by a character of a string on
the path, it cannot be occupied by another character again.
For example, the matrix below with three rows and four
columns has a path for the string “BCCED” (as highlighted in the matrix). It
does not have a path for the string “ABCB”, because the first “B” in the string
occupies the “B” cell in the matrix, and the second “B” in the string cannot
enter into the same cell again.
A

B

C

E

S

F

C

S

A

D

E

E

Analysis: It
is a typical problem about backtracking, which can be solved by storing a path
into a stack.
Firstly, it is necessary to define a structure for 2D
positions, as below:
struct Position
{
int x;
int y;
};
The movements of four directions can be defined accordingly:
Position up = {0, 1};
Position right = {1, 0};
Position down = {0, 1};
Position left = {1, 0};
Position dir[] ={up, right,
down, left};
Since paths can start from any entry in a matrix, we have to
scan every cell to check whether the character in it is identical to the first
character of the string. If it is identical, we begin to explore a path from
such a cell.
A path is defined as a stack. When a cell on path is found,
we push its position into the stack. Additionally, we also define a matrix of Boolean
masks to void entering a cell twice, which is denoted as visited. Based on these
considerations, the skeleton of solution can be implemented as the following:
bool hasPath(char* matrix, int
rows, int cols, char*
str)
{
if(matrix
== NULL  rows < 1  cols < 1  str == NULL)
return false;
bool
*visited = new bool[rows
* cols];
memset(visited, 0, rows * cols);
for(int row = 0; row < rows; ++row)
{
for(int column = 0; column < cols; ++column)
{
if(matrix[row
* cols + column] != str[0])
continue;
std::stack<Position> path;
Position position = {column, row};
path.push(position);
visited[row * cols + column] = true;
if(hasPathCore(matrix,
rows, cols, str, path, visited))
return
true;
}
}
return false;
}
Now let us analyze how to explore a path in details.
Supposing we have already found k
characters on a path, and we are going to explore the next step. We stand at the
cell corresponding to the k^{th }character
of the path, and check whether the character in its neighboring cell at up, right, down, and left side is identical to the (k+1)^{th} character of the string.
If there is a neighboring cell whose value is identical to
the (k+1)^{th} character of
the string, we continue exploring the next step.
If there is no such a neighboring cell whose value is identical
to the (k+1)^{th} character
of the string, it means the cell corresponding to the k^{th }character should not on a path. Therefore, we pop it
off a path, and start to explore other directions on the (k1)^{th }character.
Based on the analysis above, the function hasPathCore can be defined as:
bool
hasPathCore(char* matrix, int rows, int cols, char* str, std::stack<Position>& path, bool* visited)
{
if(str[path.size()]
== '\0')
return true;
if(getNext(matrix,
rows, cols, str, path, visited, 0))
return
hasPathCore(matrix, rows, cols, str, path, visited);
bool
hasNext = popAndGetNext(matrix, rows, cols, str, path, visited);
while(!hasNext
&& !path.empty())
hasNext = popAndGetNext(matrix, rows,
cols, str, path, visited);
if(!path.empty())
return
hasPathCore(matrix, rows, cols, str, path, visited);
return false;
}
The function getNext is defined to explore the (k+1)^{th} character on a path.
When it returns true, it means
the (k+1)^{th} character on a
path has been found. Otherwise, we have to pop the k^{th }character off. The function getNext is implemented as below:
bool getNext(char* matrix, int
rows, int cols, char*
str, std::stack<Position>& path, bool*
visited, int start)
{
for(int i = start; i < sizeof(dir)
/ sizeof(Position); ++i)
{
Position next = {path.top().x +
dir[i].x, path.top().y + dir[i].y};
if(next.x
>= 0 && next.x < cols
&& next.y >=0 &&
next.y < rows
&& matrix[next.y * cols +
next.x] == str[path.size()]
&& !visited[next.y * cols +
next.x])
{
path.push(next);
visited[next.y * cols + next.x] = true;
return
true;
}
}
return false;
}
When we found that the k^{th
}character should not be on a path, we call the function popAndGetNext to pop it off, and try on
other directions from the (k1)^{th
}character. This function is implemented as below:
bool
popAndGetNext(char* matrix, int rows, int cols, char* str, std::stack<Position>& path, bool* visited)
{
Position toBePoped = path.top();
path.pop();
visited[toBePoped.y * cols + toBePoped.x] =
false;
bool
hasNext = false;
if(path.size()
>= 1)
{
Position previous = path.top();
int
deltaX = toBePoped.x  previous.x;
int
deltaY = toBePoped.y  previous.y;
for(int i = 0; (i < sizeof(dir)
/ sizeof(Position) && !hasNext); ++i)
{
if(deltaX
!= dir[i].x  deltaY != dir[i].y)
continue;
hasNext = getNext(matrix, rows,
cols, str, path, visited, i + 1);
}
}
return
hasNext;
}The discussion about this problem is included in my book <Coding Interviews: Questions, Analysis & Solutions>, with some revisions. You may find the details of this book on Amazon.com, or Apress.
The author Harry He owns all the rights of this post. If you are going to use part of or the whole of this ariticle in your blog or webpages, please add a reference to http://codercareer.blogspot.com/. If you are going to use it in your books, please contact him via zhedahht@gmail.com . Thanks.
I think you have made this problem way too complicated. There is a shorter and easier understand version of it.
ReplyDeleteCould you please post the link for the "shorter and easier" version please?
DeleteExcuse me, I don't see where you remember which is the next direction that should be tried when a fallback happened on the explored path (i.e. a pop of the path stack). Can you make it clear, Thank you.
ReplyDeletestored in the stack path, basically a dfs search
DeleteThis comment has been removed by the author.
ReplyDeletepublic class StringPath {
ReplyDeletepublic static boolean isSafe(int i, int j, boolean[][] visited) {
if (i >= 0 && i < visited.length && j >= 0 && j < visited[0].length
&& !visited[i][j]) {
return true;
}
return false;
}
public static boolean findPath(char[][] mat, char[] str,
boolean[][] visited, int strIdx, int matX, int matY) {
if (strIdx >= str.length)
return true;
int[] moveX = { 1, 0, 1, 0 };
int[] moveY = { 0, 1, 0, 1 };
for (int i = 0; i < moveX.length; i++) {
for (int j = 0; j < moveY.length; j++) {
int newX = matX + moveX[i], newY = matY + moveY[i];
if (isSafe(newX, newY, visited)) {
if (mat[newX][newY] == str[strIdx]) {
visited[newX][newY] = true;
boolean result = findPath(mat, str, visited, strIdx + 1, newX,
newY);
if (!result) {
visited[newX][newY] = false;
} else {
return true;
}
}
}
}
}
return false;
}
public static void main(String[] args) {
// init visited to all false
char[][] mat = { { 'p', 'u', 'n', 'e' }, { 'd', 'i', 'k', 's' } };
char[] str = { 'p', 'd', 'i', 'k' };
boolean[][] visited = new boolean[mat.length][mat[0].length];
for (int i = 0; i < mat.length; i++) {
for (int j = 0; j < mat.length; j++) {
if (mat[i][j] == str[0]) {
if (findPath(mat, str, visited, 1, i, j)) {
System.out.println("Found it");
System.exit(0);
}
}
}
}
}
}
I believe this implementation is simpler. The basic idea is the same but you avoid the use of the visited matrix. The path of the string is not kept, it's just a matter of adding the stack as in the solution of the post.
ReplyDeletebool find_path(vector &vs, string &s) {
for (int i = 0; i < vs.size(); ++i) {
for (int j = 0; j < vs[0].size(); ++j) {
set > used_positions;
if (bt(s, 0, used_positions, i, j, vs)) return true;
}
}
return false;
}
bool bt(string &s, int match_index, set > &used_positions, int i, int j, vector &vs) {
if (match_index == s.size()) return true;
if (used_positions.count(make_pair(i, j)) > 0  i < 0  i >= vs.size()  j < 0 
j >= vs[0].size()) return false;
used_positions.insert(make_pair(i, j));
if (bt(s, match_index+1, used_positions, i1, j) 
bt(s, match_index+1, used_positions, i, j+1) 
bt(s, match_index+1, used_positions, i+1, j) 
bt(s, match_index+1, used_positions, i, j1))
return true;
return false;
}
This comment has been removed by the author.
ReplyDeleteThe outsource small tasks are valuable and meaningful when you have business where tasks are taken as challenge.
ReplyDelete