Sunday, February 19, 2012

No. 34 - String Path in Matrix


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 2-D 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 kth 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 kth character should not on a path. Therefore, we pop it off a path, and start to explore other directions on the (k-1)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 kth 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 kth character should not be on a path, we call the function popAndGetNext to pop it off, and try on other directions from the (k-1)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. 

15 comments:

  1. I think you have made this problem way too complicated. There is a shorter and easier understand version of it.

    ReplyDelete
    Replies
    1. Could you please post the link for the "shorter and easier" version please?

      Delete
  2. Excuse 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.

    ReplyDelete
    Replies
    1. stored in the stack path, basically a dfs search

      Delete
  3. This comment has been removed by the author.

    ReplyDelete
  4. public class StringPath {

    public 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);
    }
    }
    }
    }
    }
    }

    ReplyDelete
  5. 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.

    bool 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, i-1, 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, j-1))
    return true;
    return false;
    }

    ReplyDelete
  6. This comment has been removed by the author.

    ReplyDelete
  7. The outsource small tasks are valuable and meaningful when you have business where tasks are taken as challenge.

    ReplyDelete
  8. def _boggle(A, w, k, i, j, visited):
    if k>=len(w):
    return True
    for i1 in [-1,0,1]:
    for j1 in [-1,0,1]:
    ii = i + i1
    jj = j + j1
    if (i1!=0 or j1!=0) and ii>=0 and ii=0 and jj<A.shape[1] and w[k] == A[ii,jj] and visited[ii, jj]==False:
    cv=visited.copy()
    cv[ii][jj] = True
    if _boggle(A, w, k+1, ii, jj, cv):
    print (ii, jj)
    return True
    return False


    def boggle_play(A, w):
    visited = np.array([False]*A.shape[0]*A.shape[1])
    visited.shape=A.shape
    for i in range(A.shape[0]):
    for j in range(A.shape[1]):
    visited[i, j] = True
    if A[i,j] == w[0] and _boggle(A, w, 1, i, j, visited.copy()):
    print ('f',i, j)
    return True
    visited[i, j] = False
    return False

    A=np.array(['A','B','C','D','A','B','C','D','A','B','C','D','A','B','C','D'])
    A.shape=[4,-1]
    print(A)
    print(boggle_play(A, 'AAAABCCDDDD'))

    ReplyDelete
  9. Salve


    Thanks for highlighting this and indicating about #topic where more study and thought is necessary.
    When I log into the AWS Console via Firefox 57 (and even sometimes Chrome) the body of the console fails to load a large percentage of the time. When this happens, I can only see the navbar and the footer of the page, and the console is rendered useless to me. This seems to happen periodically and then resolves after some waiting. AWS Tutorial
    Sometimes even the navbar and footer don't render and I just see some copyright text in the corner. This seriously impairs my ability to use the console and could be revenue-impacting.






    Once again thanks for your tutorial.


    Thank you,
    Ajeeth

    ReplyDelete
  10. Hi Bru,


    I’ve often thought about this No. 34 - String Path in Matrix. Nice to have it laid out so clearly. Great eye opener.

    I'd like to make a suggestion to improve the user experience for setting up a Reserved Instance. This comes from my own experience of using RIs on both EC2 and RDS (which is why I haven't put this in a product specific forum). AWS Tutorial






    But nice Article Mate! Great Information! Keep up the good work!


    Thanks a heaps,
    Ajeeth

    ReplyDelete
  11. Hi Buddie,


    I’ve often thought about this No. 34 - String Path in Matrix. Nice to have it laid out so clearly. Great eye opener.

    Sorry if this is a stupid question, but I signed up my company for an AWS account. The traditional AWS homepage dashboard is not there in my new account. Instead I have "Shortcuts and Recently Viewed Services" and a few bigger icon shortcuts. AWS Tutorial






    Super likes !!! for this amazing post. I thinks everyone should bookmark this.


    Gracias
    Ajeeth

    ReplyDelete
  12. Salaam,


    I learnt so much in such little time about No. 34 - String Path in Matrix . Even a toddler could become smart reading of your amazing articles.


    Thank you for creating an Amazon Web Services (AWS) account. AWS Tutorial We are in the process of activating your account so that you can begin using AWS. For most customers, activation only takes a couple of minutes (but can sometimes take a few hours if additional account verification is required). We will notify you by email once verification is complete and your account is activated."





    Appreciate your effort for making such useful blogs and helping the community.


    Thanks,
    Irene Hynes

    ReplyDelete