**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.
AkashFor better viewing of code, please copy-paste in the editor of your choice or click on 'view plain'.

AnonymousI think one can use bfs+floodfill to solve this problem visiting all neighbors and queueing matches.

Anonymousso as u said in last i think time complexity in case og AAAAAA....B will be O(N^2) ins't it ?

Anonymousck its giving wrong answer in case of "microsoft" here

https://ideone.com/kau2V

Akash@Anonymous 1: Can you please explain in detail?

@Anonymous 2: No. it won't be O(N^2) but exponential. Seems not a very good solution as it has horrendous complecity in worst case.

@Anonymous 3: At this link, we see answer as 'false' coz you provide {'x','s','o','p','s'} in place of {'x','s','o','p','c'} in 2nd row of the matrix.

Anonymous@Akash Can You Please Explain Hows The Time Complexity Will be Exponential in worst case ?? i am not getting it ? please explain briefly .

phoxis.orgA DFS works here. For each cell visit all the adjacent cells and check for a match in a DFS way. This works: https://ideone.com/KWOWp

Akash@phoxis: Though I didn't check its correctness but definitely a cleaner code. Unfortunately, complexity is as bad or worse than it was.

For worst case in MAX=3, iterations: 76193

For worst case in MAX=4, iterations: 25766480

For worst case definition, please read last part of the post and try yourself.

phoxis.orgYes, it goes without saying that the solution i presented has a really nasty worst case growth. But being exhaustive it will get a definite answer, although i am also yet to prove the correctness.

I tried something on the implementation you presented with some other input, which fails to detect the pretense of the pattern. Here is the code: https://ideone.com/5tr7L Here i search the string "afti". The original matrix is the one you presented in the post. Can you have a look what might be the problem ?

The exhaustive solution i presented finds it: https://ideone.com/v3kuG Also marks multiple occurrences.

Still, finding a better solution which can prune out unnecessary checks.

Akash@phoxis: I am also seeing some problem with "afti". Will look into it. Thanks for pointing it out.

Omar Mohammad OthmanYou have to remove the call for strlen(pat) and send this as a parameter, since this method is linear. This multiplies your complexity by a factor of p (the length of the pattern)!

phoxis.org@Omar Mohammad Othman: Yes right, i have updated the code in my blog post.

AnonymousThere is a bug in the code. The reason the pattern "AFTI" doesn't work is because there is another 'A' before it gets to the right 'A'. The 'A' at x=0,y=0 makes the code go into the else if, but all neighbor match return false, so the code returns false without even trying the next cell. The code needs to be rearranged so that if there is a failure at subsequent levels then the preceding level needs to continue to the next cell

Anonymousyes the complexity would be (N^2)*(4^n)

for each of the element it will try till (n-1)th depth in all 4 direction and fail.

UpasanaI guess we can do it in O(n) time complexity using an array of size 26.

lets parse the given string once and update the array index es with count(frequency of each number). Lets say MICROSOFT. So array[0] = 0x0 because 'a' did not appear in the string similarly index for 'o' reads 2.. now parse the given matrix. See if the current character is already present in the array, If yes, decrease its count. after parsing the whole matrix, parse the array and see if any index has non-zero value. If yes, the string is not found.

Akash@Upasana: Bt this method, you are just confirming if all the pattern characters are present in matrix or not. It will not guarantee if pattern is present as a path in the matrix.

Vijay Kasiviswanathanpublic class MatrixSearch {

public static void main(String[] args) {

String[] find = {"M", "I", "C", "R", "O", "S", "O", "F", "T"};

String[][] matrix = {

{"A", "C", "P", "R", "C"},

{"M", "S", "O", "P", "C"},

{"I", "O", "V", "N", "I"},

{"C", "G", "F", "M", "N"},

{"Q", "A", "T", "I", "T"}

};

// printing matrix...

for (int i = 0; i < matrix.length; i++) {

for (int j = 0; j < matrix[i].length; j++) {

System.out.print(matrix[i][j]);

}

System.out.println("");

}

for (int i = 0; i < matrix.length; i++) {

for (int j = 0; j < matrix[i].length; j++) {

if (matrix[i][j].equals(find[0])) {

System.out.println(matrix[i][j]);

boolean found = recursiveMatrixFind(matrix, i, j, matrix.length, matrix.length, find, 1);

System.out.println(found);

}

}

}

}

public static boolean recursiveMatrixFind(String[][] matrix, int row, int column, int rowLength, int columnLength, String[] find, int k) {

if (k == find.length) {

return true;

}

for (int neighbourRow = row - 1; neighbourRow <= row + 1; neighbourRow++) {

if (neighbourRow >= 0 && neighbourRow < rowLength) {

for (int neighbourColumn = column - 1; neighbourColumn <= column + 1; neighbourColumn++) {

if (neighbourColumn >= 0 && neighbourColumn < columnLength) {

if ((!(neighbourRow == row && neighbourColumn == column))) {

if (matrix[neighbourRow][neighbourColumn].equals(find[k])) {

System.out.println(matrix[neighbourRow][neighbourColumn]);

boolean found = recursiveMatrixFind(matrix, neighbourRow, neighbourColumn, rowLength, columnLength, find, ++k);

if (found) {

return true;

} else {

continue;

}

}

}

}

}

}

}

return false;

}

}