A 2-D grid of characters is given. For e.g. A 5x4 matrix is as follows :
{{'M','O','B','S','N'},
{'M','O','I','L','E'},
{'M','B','I','L','E'},
{'O','B','I','L','E'}}.
I have to find how many times the word "MOBILE" occurs in above grid using Java. For above the answer would be 3. I can traverse only in 4 directions, i.e. right, left, up, down. (NOT DIAGONALLY).
Another example :
{{'c','a','r'},
{'a','r','c'},
{'c','r','a'}}
and the word is "car". Answer for this grid would be 5.
I am aware of the fact that backtracking would help but HOW?
CodePudding user response:
If matrix has N elements, search string is k chars, there are m copies in matrix:
First, find all positions of first letter of string in matrix. O(N)
Then for each found position, do 4-way scan for n-1 characters. O(k*m)
Finally, sum all search results. O(m)
CodePudding user response:
Following is the solution to my own question. It took me a while to figure out. P.S. I've developed the solution ignoring any possibility of pallindromes.
import java.util.*;
class WOG{
static int m = 0;
static int n = 0;
static int[] x = {0,-1,0,1};
static int[] y = {-1,0,1,0};
public static int func(char[][] grid, int row, int col, String word, int k){
int occ = 0;
if(row>=m || row<0 || col<0 || col>=n)
return 0;
if(grid[row][col]!=word.charAt(k))
return 0;
if(k==word.length()-1)
return 1;
for(int dir=0;dir<4;dir ){
int rd = row x[dir];
int cd = col y[dir];
occ = func(grid,rd,cd,word,k 1);
}
return occ;
}
public static int pattern(char[][] grid, String word){
int res = 0;
for(int i=0;i<m;i ){
for(int j=0;j<n;j ){
res = func(grid,i,j,word,0);
}
}
return res;
}
public static void main(String[] args){
char[][] grid2 = {{'m','o','b','s','n'},
{'m','o','i','l','e'},
{'m','b','i','l','e'},
{'o','b','i','l','e'}};
char[][] grid = {{'c','a','r'},
{'a','r','c'},
{'c','r','a'}};
m = 4;
n = 5;
int ans = pattern(grid2,"mobile");
System.out.println(ans);
}
}
I've made use of recursion and backtracking.