Question: You are given a 2D array of characters and a character pattern. WAP to find if pattern is present in 2D array. Pattern can be in any way (all 8 neighbors to be considered) but you can’t use same character twice while matching. Return 1 if match is found, 0 if not.

Example: Find “microsoft” in below matrix.


We can see the read color character, which form “Microsoft” in above 2D array.

Answer: I was asked this question in a Microsoft interview almost a year ago. A reader asked me to post the solution for this.

Manually finding the solution of this problem is relatively intuitive, we just need to describe an algorithm for it. Ironically, describing the algorithm is not the easy part.

How do we do it manually? First we match the first element; if it matched we matched the 2nd element in the 8 neighbors of first match; do this process recursively; when last character of input pattern matches, return true.

During above process, you take care not to use any cell in 2D array twice. For this purpose, you mark every visited cell with some sign. If your pattern matching fails at some place, you start matching from the beginning (of pattern) in remaining cells. While returning, you unmark visited cells.

Lets convert above intuitive method in algorithm. Since we are doing similar checks every time for pattern matching, a recursive solution is what we need here.

In recursive solution, we need to check if the substring passed is matched in the given matrix or not. The condition is not to use the already used cell. For finding already used cell, we need to have another 2D array to the function (or we can use an unused bit in input array itself.) Also, we need the current position of input matrix, from where we need to start. Since we need to pass a lot more information than actually given, we should be having a wrapper function to initialize that extra information to be passed.

Algorithm:

If you are past the last character in pattern
    Return true

If you got an used cell again
    Return falseIf you got past the 2D matrix  
    Return false

If searching for first element and cell doesn’t match
    findmatch with next cell in row-first order (or column first order)

otherwise if character matches
    mark this cell as used
    res = findmatch with next position of pattern in 8 neighbors
    mark this cell as unused
    Return res

Otherwise
    Return false

Code:

 
#define MAX 100


//level: index till which pattern is matched
//x, y: current position in 2D array
bool findmatch(char mat[MAX][MAX], char *pat, int x, int y, int nrow, int ncol, int level)
{
    if (level == strlen(pat)) //pattern matched
        return true;
        
    if (x<0 || y<0 || x>=nrow || y>=ncol)
     return false; 
    
    if (mat[x][y] == pat[level])
    {
     // printf("{%d, %d}\n",x,y);
        bool res;

        //marking this cell as used
        char temp = mat[x][y];
        mat[x][y] = '#';       
             
        //finding subpattern in 8 neighbours     
        res = findmatch(mat, pat, x-1, y, nrow, ncol, level+1)   ||
              findmatch(mat, pat, x+1, y, nrow, ncol, level+1)   ||
              findmatch(mat, pat, x, y-1, nrow, ncol, level+1)   ||
              findmatch(mat, pat, x, y+1, nrow, ncol, level+1)   ||
              findmatch(mat, pat, x+1, y+1, nrow, ncol, level+1) ||
              findmatch(mat, pat, x+1, y-1, nrow, ncol, level+1) ||
              findmatch(mat, pat, x-1, y+1, nrow, ncol, level+1) ||
              findmatch(mat, pat, x-1, y-1, nrow, ncol, level+1);

        //marking this cell as unused
        mat[x][y] = temp;
        return res;
    }
    else
        return false;
}

bool findmatch_wrapper(char mat[MAX][MAX], char *pat, int nrow, int ncol)
{
 // if total characters in matrix is less then pattern lenghth
    if (strlen(pat) > nrow*ncol)
        return false;

    for (int i=0; i<nrow; i++)
     for (int j=0; j<ncol; j++){

      if (mat[i][j] == pat[0])
                    if(findmatch(mat, pat, i, j, nrow, ncol, 0)) 
                          return true;
     }
    return false;
}


Please note the use of OR operator while calculating res. This confirms me that I don’t evaluate next condition as soon as one of the conditions evaluates to true.

Complexity:
Best case complexity is obviously O(1), if pattern is NULL.

Worst case: What will be worst case for this problem. The matrix (lets say N*N) is filled with ‘A’ in all the cells and pattern is “AAAA…….AAAAB” of length N^2. Then it will match with every cell, search in 8 neighbors recursively and fails at last element every time.

I'm leaving it to readers to find the complexity of this approach.


Subscribe - To get an automatic feed of all future posts subscribe here, or to receive them via email go here and enter your email address in the box. You can also like us on facebook and follow me on Twitter @akashag1001.